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 <= 100
- 0 <= 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, val=0, next=None):
# 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 slow
2. 连成环后截断
时间
24ms
击败 53.42%使用 Python 的用户
内存
12.51mb
击败 97.52%使用 Python 的用户
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def rotateRight(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""p = head# 长度计算n = 1while p and p.next:n+=1p = 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