算法第三十七天-旋转链表

旋转链表

题目要求

解题思路

题意：将链表中每个元素向后移动k个位置，相当于把链表的后面k%len节点移到链表的最前面。
所以本题步骤为：
1.求出链表长度；
2.找出倒数第k+1个节点
3.链表重整：将连败哦的倒数第k+1个节点和倒数第k个节点断开，并把后半部分拼接到链表的头部

1.求链表的长度

求链表长度应该是链表最基本的题型了，直接用一个指针cur，开始时指向链表的头head，一直向后移动到cur为空时，经历的链表节点数就是链表长度。

2.找出倒数第k+1个节点

思路是：
1.两个指针slow和fast值距离是k，先让fast指向链表的第k+1个节点，slow指向第1个节点；
2.然后slow和fast同时向后移动，当fast移动到链表的最后一个节点的时候，那么slow指向链表的倒数第k+1个节点。

3.链表重整

重整操作步骤是：
1.newHead是新链表的头部，它应该是原链表倒数第k个节点，即slow.next；
2.slow需要跟slow.next断开；
3.fast是老链表的结尾，将fast.next设置为老链表的开头，实现首位相接。
可以用下面的图来帮助理解：链表是1->2->3->4->5->null,k=2。图中①是让fast指向第k+1个节点；图中②是fast和slow同时后移至链表结尾，此时slow指向链表倒数第k+1个节点；图中③是链表重整的操作。

代码

# 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: ListNode, k: int) -> ListNode:
        if not head or not head.next:
            return head
        _len=0
        cur = head
        while cur:
            _len +=1
            cur=cur.next
        k %= _len
        if k == 0: return head
        slow,fast=head,head
        for i in range(k):
            fast=fast.next
        while fast.next:
            fast=fast.next
            slow = slow.next
        newHead =slow.next
        slow.next = None
        fast.next=head
        return newHead

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(1)$