题目

给定一个链表，旋转链表，将链表每个节点向右移动 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. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func rotateRight(head *ListNode, k int) *ListNode {
  9.     if head == nil || head.Next == nil {
  10.         return head
  11.     }
  12.     length := 0
  13.     node := head
  14.     for node != nil {
  15.         length += 1
  16.         node = node.Next
  17.     }
  19.     for i := 0; i < k % length; i++ {
  20.         head = rotateOne(head)
  21.     }
  22.     return head
  23. }
  25. func rotateOne(head *ListNode) *ListNode {
  26.     node := head
  27.     var prev *ListNode
  28.     for node.Next != nil {
  29.         prev = node
  30.         node = node.Next
  31.     }
  32.     prev.Next = nil
  33.     node.Next = head
  34.     return node
  35. }
  • 时间复杂度 旋转链表 - 图1

方案二（双指针）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func rotateRight(head *ListNode, k int) *ListNode {
  9.     if head == nil || head.Next == nil {
  10.         return head
  11.     }
  12.     // 找到最小的k
  13.     length := 0
  14.     node := head
  15.     for node != nil {
  16.         length += 1
  17.         node = node.Next
  18.     }
  19.     k = k % length
  20.     if k == 0 {
  21.         return head
  22.     }
  23.     // 双指针
  24.     firstPtr := head
  25.     secondPtr := head
  26.     i := 0
  27.     for firstPtr.Next != nil {
  28.         firstPtr = firstPtr.Next
  29.         i += 1
  30.         if i > k {
  31.             secondPtr = secondPtr.Next
  32.         }
  33.     }
  35.     new_head := secondPtr.Next
  36.     secondPtr.Next = nil
  37.     firstPtr.Next = head
  38.     return new_head
  39. }
  • 时间复杂度 旋转链表 - 图2；
  • 空间复杂度 旋转链表 - 图3
  • 第一次使用快慢指针得到链表的长度；
  • 第二次使用窗口大小为 旋转链表 - 图4 的双指针；
  • 找到节点后翻转即可。

方案三（双指针+数组）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * type ListNode struct {
  4.  *     Val int
  5.  *     Next *ListNode
  6.  * }
  7.  */
  8. func rotateRight(head *ListNode, k int) *ListNode {
  9.     if head == nil || head.Next == nil {
  10.         return head
  11.     }
  12.     list := []*ListNode{}
  13.     for head != nil {
  14.         list = append(list, head)
  15.         head = head.Next
  16.     }
  18.     k = k % len(list)
  19.     if k == 0 {
  20.         return list[0]
  21.     }
  22.     new_head := list[len(list) - k]
  23.     list[len(list) - k - 1].Next = nil
  24.     list[len(list) - 1].Next = list[0]
  25.     return new_head
  26. }
  • 时间复杂度 旋转链表 - 图5
  • 空间复杂度 旋转链表 - 图6
  • 参考 leetcode 答案得出上述方案

原文

https://leetcode-cn.com/explore/learn/card/linked-list/197/conclusion/767/