Question

61. 旋转链表

English Version

题目描述

给你一个链表的头节点 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

解法

方法一：快慢指针 + 链表拼接

我们先判断链表节点数是否小于 $2$，如果是，直接返回 $head$ 即可。

否则，我们先统计链表节点数 $n$，然后将 $k$ 对 $n$ 取模，得到 $k$ 的有效值。

如果 $k$ 的有效值为 $0$，说明链表不需要旋转，直接返回 $head$ 即可。

否则，我们用快慢指针，让快指针先走 $k$ 步，然后快慢指针同时走，直到快指针走到链表尾部，此时慢指针的下一个节点就是新的链表头节点。

最后，我们将链表拼接起来即可。

时间复杂度 $O(n)$，其中 $n$ 是链表节点数，空间复杂度 $O(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: Optional[ListNode], k: int) -> Optional[ListNode]:
    if head is None or head.next is None:
      return head
    cur, n = head, 0
    while cur:
      n += 1
      cur = cur.next
    k %= n
    if k == 0:
      return head
    fast = slow = head
    for _ in range(k):
      fast = fast.next
    while fast.next:
      fast, slow = fast.next, slow.next

    ans = slow.next
    slow.next = None
    fast.next = head
    return ans

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode() {}
 *   ListNode(int val) { this.val = val; }
 *   ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode cur = head;
    int n = 0;
    for (; cur != null; cur = cur.next) {
      n++;
    }
    k %= n;
    if (k == 0) {
      return head;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (k-- > 0) {
      fast = fast.next;
    }
    while (fast.next != null) {
      fast = fast.next;
      slow = slow.next;
    }
    ListNode ans = slow.next;
    slow.next = null;
    fast.next = head;
    return ans;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode() : val(0), next(nullptr) {}
 *   ListNode(int x) : val(x), next(nullptr) {}
 *   ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* rotateRight(ListNode* head, int k) {
    if (!head || !head->next) {
      return head;
    }
    ListNode* cur = head;
    int n = 0;
    while (cur) {
      ++n;
      cur = cur->next;
    }
    k %= n;
    if (k == 0) {
      return head;
    }
    ListNode* fast = head;
    ListNode* slow = head;
    while (k--) {
      fast = fast->next;
    }
    while (fast->next) {
      fast = fast->next;
      slow = slow->next;
    }
    ListNode* ans = slow->next;
    slow->next = nullptr;
    fast->next = head;
    return ans;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
  if head == nil || head.Next == nil {
    return head
  }
  cur := head
  n := 0
  for cur != nil {
    cur = cur.Next
    n++
  }
  k %= n
  if k == 0 {
    return head
  }
  fast, slow := head, head
  for i := 0; i < k; i++ {
    fast = fast.Next
  }
  for fast.Next != nil {
    fast = fast.Next
    slow = slow.Next
  }
  ans := slow.Next
  slow.Next = nil
  fast.Next = head
  return ans
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 *   }
 * }
 */

function rotateRight(head: ListNode | null, k: number): ListNode | null {
  if (!head || !head.next) {
    return head;
  }
  let cur = head;
  let n = 0;
  while (cur) {
    cur = cur.next;
    ++n;
  }
  k %= n;
  if (k === 0) {
    return head;
  }
  let fast = head;
  let slow = head;
  while (k--) {
    fast = fast.next;
  }
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  const ans = slow.next;
  slow.next = null;
  fast.next = head;
  return ans;
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//   ListNode {
//     next: None,
//     val
//   }
//   }
// }
impl Solution {
  pub fn rotate_right(mut head: Option<Box<ListNode>>, mut k: i32) -> Option<Box<ListNode>> {
    if head.is_none() || k == 0 {
      return head;
    }
    let n = {
      let mut cur = &head;
      let mut res = 0;
      while cur.is_some() {
        cur = &cur.as_ref().unwrap().next;
        res += 1;
      }
      res
    };
    k = k % n;
    if k == 0 {
      return head;
    }

    let mut cur = &mut head;
    for _ in 0..n - k - 1 {
      cur = &mut cur.as_mut().unwrap().next;
    }
    let mut res = cur.as_mut().unwrap().next.take();
    cur = &mut res;
    while cur.is_some() {
      cur = &mut cur.as_mut().unwrap().next;
    }
    *cur = head.take();
    res
  }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   public int val;
 *   public ListNode next;
 *   public ListNode(int val=0, ListNode next=null) {
 *     this.val = val;
 *     this.next = next;
 *   }
 * }
 */
public class Solution {
  public ListNode RotateRight(ListNode head, int k) {
    if (head == null || head.next == null) {
      return head;
    }
    var cur = head;
    int n = 0;
    while (cur != null) {
      cur = cur.next;
      ++n;
    }
    k %= n;
    if (k == 0) {
      return head;
    }
    var fast = head;
    var slow = head;
    while (k-- > 0) {
      fast = fast.next;
    }
    while (fast.next != null) {
      fast = fast.next;
      slow = slow.next;
    }
    var ans = slow.next;
    slow.next = null;
    fast.next = head;
    return ans;
  }
}