赞
踩
给你一个链表的头节点 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
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if k == 0 or not head or not head.next: return head _head = head total = 0 while _head: total += 1 _head = _head.next _k = k % total if _k == 0: return head dummy = ListNode(next=head) slow = fast = dummy while fast.next: if _k < 1: slow = slow.next fast = fast.next _k -= 1 first = slow.next slow.next = None # forth second = fast third = dummy.next dummy.next = first second.next = third return dummy.next
看了一眼官解,发现是先连成环然后再断开,比上面的思路时间复杂度常数更小,Python 实现如下
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if k == 0 or not head or not head.next: return head _head = head total = 1 while _head.next: total += 1 _head = _head.next _head.next = head count = total - k % total while count: _head = _head.next count -= 1 res = _head.next _head.next = None return res
时间复杂度O(n)
空间复杂度O(1)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。