题目

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例1

  1. 输入: 1->2->3->4->5->NULL, k = 2
  2. 输出: 4->5->1->2->3->NULL
  3. 解释:
  4. 向右旋转 1 步: 5->1->2->3->4->NULL
  5. 向右旋转 2 步: 4->5->1->2->3->NULL

示例2

  1. 输入: 0->1->2->NULL, k = 4
  2. 输出: 2->0->1->NULL
  3. 解释:
  4. 向右旋转 1 步: 2->0->1->NULL
  5. 向右旋转 2 步: 1->2->0->NULL
  6. 向右旋转 3 步: 0->1->2->NULL
  7. 向右旋转 4 步: 2->0->1->NULL

实现

思路1

通过观察示例1我们很容易可以发现，当k<n时，输出链表的头的位置就是输入链表的n-k处，而尾部就是n-k-1处。观察示例2可以发现，当k>=n时，新的链表头就在n-k%n处，而尾部就是n-k%n-1处。
于是实现就变得很简单：

  1. 首先将输入链表的尾部连接到头部，使其闭合为环；
  2. 按之前的计算方法找到新的链表头部和尾部的位置，在其中间断开（tail.next = nullPtr)即可
  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def rotateRight(self, head: ListNode, k: int) -> ListNode:
  8.         if not head:
  9.             return None
  10.         if not head.next:
  11.             return head
  13.         tail = head
  14.         n = 1
  15.         while tail.next:
  16.             tail = tail.next # 找到旧链表尾部
  17.             n += 1  # 链表长度
  18.         # 闭环
  19.         tail.next = head
  21.         for i in range(n - k % n):
  22.             tail = tail.next  # 找到新链表尾部
  23.         new_head = tail.next
  25.         # 把环断开
  26.         tail.next = None
  28.         return new_head

时间复杂度：，N为链表中的元素个数。因为需要对链表遍历一遍找到链表尾部。