襄阳市住房城乡建设部网站,广西网站建设与规划,安徽华力建设集团网站,长春百度网站快速排名61. 旋转链表 题目-中等难度示例1. 快慢指针找到分割位置2. 连成环后截断 题目-中等难度
相关企业 给你一个链表的头节点 head #xff0c;旋转链表#xff0c;将链表每个节点向右移动 k 个位置。
示例
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], k 2 输出… 61. 旋转链表 题目-中等难度示例1. 快慢指针找到分割位置2. 连成环后截断 题目-中等难度
相关企业 给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。
示例
示例 1 输入head [1,2,3,4,5], k 2 输出[4,5,1,2,3] 示例 2 输入head [0,1,2], k 4 输出[2,0,1] 提示* 链表中节点的数目在范围 [0, 500] 内-100 Node.val 1000 k 2 * 109 来源力扣LeetCode 链接https://leetcode.cn/problems/summary-ranges 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
1. 快慢指针找到分割位置
时间 20ms 击败 81.37%使用 Python 的用户 内存 12.63mb 击败 83.54%使用 Python 的用户
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def rotateRight(self, head, k)::type head: ListNode:type k: int:rtype: ListNode# 先计算链表长度p headl 0while p:l 1p p.nextif l 1 or k 0:return head# 快慢指针fast slow head# 让快指针先行k%l个位置for i in range(k%l):fast fast.next# 然后让快指针行到最后节点位置慢指针则是后半链表的头节点位置nn ListNode(-1)cur nnwhile fast:fast fast.nextcur.next ListNode(slow.val)slow slow.nextcur cur.next# 如果slow存在, 得到slow的最后一个节点位置, 拼接nnif slow:r slowelse:return nn.nextwhile r and r.next:r r.next# slow 排除头节点的nnr.next nn.nextreturn slow2. 连成环后截断
时间 24ms 击败 53.42%使用 Python 的用户 内存 12.51mb 击败 97.52%使用 Python 的用户
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def rotateRight(self, head, k)::type head: ListNode:type k: int:rtype: ListNodep head# 长度计算n 1while p and p.next:n1p p.next# 如果k为0 或者n小于等于1if(k 0) or n 1:return head# nnt 获取截断位置nt head# 成环p.next head# 获取截断点for i in range(n - k % n - 1):nt nt.next# 结果头res nt.next# 截断循环nt.next Nonereturn res
