题解 | #旋转链表#

题目分析

1. 题目给出了我们一条链表得头结点指针，和一个整数值k
2. 题目要求我们根据给出得整数值k，开始将链表最后一个节点添加到头节点之前，重复此过程k次，返回当前的链表头节点

方法一：快慢指针

• 实现思路
  • 我们先用一个指针将链表长度计算出来
  • 然后将给定的k对链表长度取余，减少时间代价
  • 先让快指针从头节点开始向前迭代k步
  • 再让慢指针从起点出发，和快指针同时向后迭代
  • 到快指针迭代到链表尾，慢指针停留的位置即新的链表末尾节点，慢指针下一个节点即新链表的首节点，最终返回新链表头即可

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def rotateLinkedList(self , head: ListNode, k: int) -> ListNode:
        # write code here
        if not head:
            return None
        
        # 找出链表的长度
        cur = head
        length = 0
        while cur:
            length += 1
            cur = cur.next
        
        # 快指针先行
        k = k % length
        fast = head
        step = k
        while step > 0:
            fast = fast.next
            step -= 1
        
        # 慢指针后行
        slow = head
        while fast.next:
            slow = slow.next
            fast = fast.next
        
        # 重新组织链表
        fast.next = head
        ret = slow.next
        slow.next = None
        return ret

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中$nn$是链表长度，遍历链表长度的时间代价
• 空间复杂度：$O(1)O(1)$，只引入了常量级别的空间代价

方法二：单指针

• 实现思路

  • 首先同样和方法一一样，找到链表长度$nn$

  • 将k对长度取余，简化时间开销

  • 然后将链表首尾相接，链表成环，从尾节点指针继续向后迭代$n-k\mathrm{\%}nn\; -\; k\; \backslash \%\; n$次

  • 现在指针的位置就是需要解环的位置，下一个节点即需要返回的头节点

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def rotateLinkedList(self , head: ListNode, k: int) -> ListNode:
        # write code here
        if not head:
            return None
        
        # 找出链表的长度
        cur = head
        length = 1
        while cur.next:
            length += 1
            cur = cur.next
        
        # 将链表成环，找到最终需要解环的位置
        cur.next = head
        m = length - k % length
        while m:
            cur = cur.next
            m -= 1
        
        # 链表解环，返回头指针
        ret = cur.next
        cur.next = None
        return ret

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中$nn$是链表长度，遍历链表长度的时间代价
• 空间复杂度：$O(1)O(1)$，只引入了常量级别的空间代价