LeetCode Rotate List: Two Pointers

Overview

This LeetCode Rotate List  is to test you pointer manipulation skills, keep two points, without knowing the actual length of the linked list we can rotate it.

LeetCode Rotate List

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

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Solution Analysis: Two Pointers

1) You can first find the length of the list, and mod k, that is k %= len, since k might be larger than the length of the list. Ok, then you just scan the list from the head and get the pointer of the pivot node (e.g. 4 in the above example), the pivot node partition the list into left and right part, if you include the pivot node into the right part, then ok, you just exchange these two left and right list, and concatenate the left list onto the tail of the right list. The resulted list is the rotated list.

2) By keeping two pointers, and make their distance be k, and make the second pointer pointing to the tail of the list, we can implement the above same idea without knowing the actual length. The following code implement this not knowing the length of linked list version of code and is accepted by LeetCode OJ to pass this Rotate List problem

ListNode *rotateRight(ListNode *head, int k) {
    if (k == 0 || NULL == head || NULL == head->next)
        return head;

    ListNode s(0);
    s.next = head;
    ListNode *p1(head), *p2(head);
    ListNode *p0(&s);

    while (--k) {
        if (NULL == p2->next)
            p2 = p1;
        else
            p2 = p2->next;
    }

    while (p2->next) {
        p0 = p0->next;
        p1 = p1->next;
        p2 = p2->next;
    }

    p0->next = NULL;
    p2->next = s.next;

    return p1;
}

More test cases: 1->2->NULL, k – 1. 1->2->NULL, k = 2, 1 -> 2 -> NULL k = 3.

Summary

This LeetCode Rotate List  is to test you pointer manipulation skills, keep two points, without knowing the actual length of the linked list we can rotate it.

Written on May 20, 2013