61. Rotate List

Leetcode Linked List Two Pointers

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

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

/**
 * 这道题目是将链表右移k位，由于在链表末尾删除元素是比较麻烦的，所以将链表左移length-k位，其中length为链表长度。
 * 1. 链表左移时，即在链表末尾添加元素，从链表首部删除元素。用两个指针分别指向这两个位置，然后分别移动。
 * 2. 只记录将要移动的length-k位位置，然后再移动
 */

/**
 * Link: https://leetcode.com/problems/rotate-list/description/
 */
public class Q61RotateListv1 {

    /**
     * 链表左移时，即在链表末尾添加元素，从链表首部删除元素
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head==null) {
            return head;
        }
        // length of list
        int length = 1;
        ListNode pos = head;
        ListNode first = head;
        while(pos.next!=null) {
            pos = pos.next;
            length++;
        }

        // rotate to right
        for (int i = 0; i < length - k % length; i++) {
            pos.next = first;
            pos = pos.next;
            first = first.next;
        }
        pos.next = null;
        return first;
    }

    /**
     * 只记录将要移动的length-k位位置，然后再移动.
     */

    public ListNode rotateRight(ListNode head, int k) {
        if (head==null) {
            return head;
        }

        // length of list
        int length = 1;
        ListNode pos = head;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }

        // Get the length-n%length th node
        for (int i = 1; i < length - k % length; i++) {
            pos = pos.next;
        }

        // do the rotation
        tail.next = head;
        head = pos.next;
        pos.next = null;
        return head;
    }
}