Rotate List

Question

Problem Statement

Given a list, rotate the list to the right by k places, where k is non-
negative.

Example

Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3.

题解

旋转链表，链表类问题通常需要找到需要处理节点处的前一个节点。因此我们只需要找到旋转节点和最后一个节点即可。需要注意的细节是 k 有可能比链表长度还要大，此时需要取模，另一个 corner case 则是链表长度和 k 等长。

Java

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     /**
  14.      * @param head: the List
  15.      * @param k: rotate to the right k places
  16.      * @return: the list after rotation
  17.      */
  18.     public ListNode rotateRight(ListNode head, int k) {
  19.         if (head == null) return head;
  20.         ListNode fast = head, slow = head;
  21.         int len = 1;
  22.         for (len = 1; fast.next != null && len <= k; len++) {
  23.             fast = fast.next;
  24.         }
  25.         // k mod len if k > len
  26.         if (len <= k) {
  27.             k = k % len;
  28.             fast = head;
  29.             for (int i = 0; i < k; i++) {
  30.                 fast = fast.next;
  31.             }
  32.         }
  33.         // forward slow and fast
  34.         while (fast.next != null) {
  35.             fast = fast.next;
  36.             slow = slow.next;
  37.         }
  38.         // return new head
  39.         fast.next = head;
  40.         head = slow.next;
  41.         slow.next = null;
  43.         return head;
  44.     }
  45. }

源码分析

由于需要处理的是节点的前一个节点，故最终的while 循环使用fast.next != null. k 与链表等长时包含在len <= k中。

复杂度分析

时间复杂度 O(n), 空间复杂度 O(1).