P111 旋转单链表

描述#

这个题目说的是，给你一个单链表和一个数字 k，你要把链表右边的节点旋转到链表左边，共旋转 k 次。

比如说，给你的单链表是：
0 -> 1 -> 2 -> 4 -> 8
给你的数字 k 是 3：
k = 3
把链表右边的节点一个个旋转到左边，操作 3 次。先是节点 8，然后是节点 4，最后是节点 2。
剩下的节点 0 和 1 保持不动。最后得到旋转后的链表是：
2 -> 4 -> 8 -> 0 -> 1

代码#

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(1)
  public ListNode rotateRightToLeft(ListNode head, int k) {
    if (head == null || head.next == null || k <= 0) return head;
    ListNode end = head;
    int n = 1;
    for (; end.next != null; end = end.next) ++n;
    end.next = head;

    k %= n;
    ListNode newEnd = head;
    for (int i = 0; i < n-k-1; ++i) newEnd = newEnd.next;
    ListNode newHead = newEnd.next;
    newEnd.next = null;
    return newHead;
  }

}