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.

linkedlist题,就是要注意处理n=0和n>length的情况,就是平移超过一圈的情况,其他就是用两个指针追踪要移动的部分,先将head移到为(离开头n%len的地方),然后再head和tail一起移动,当head到尾部的时候,tail就是要移动的部分的头。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null)
            return null;
        if (n == 0)
            return head;
        ListNode newHead = head;
        for (int i = 0; i < n-1; i++)
        {
            if (newHead.next != null)
                newHead = newHead.next;
            else
                newHead = head;
        }
        if (newHead.next == null)
            return head;
        ListNode helper = new ListNode(0);
        helper.next = head;
        ListNode newTail = helper;
        while(newHead.next != null)
        {
            newHead = newHead.next;
            newTail = newTail.next;
        }
        
        newHead.next = head;
        head = newTail.next;
        newTail.next = null;
        return head;
    }
}

Second submission:

Connecting tail to head, then move both head and tail, we can simply move the head and tail backward for n, but we do not have the information to move backward, so we can move forward (len – n )

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        //find tail first
        if (head == null) {
            return null;
        }
        if (n == 0)
            return head;
        ListNode tail = head;
        int len = 1;
        while(tail.next != null) {
            tail = tail.next;
            len++;
        }
        n = n%len; // get rid of circulation
        tail.next = head; // connect tail to head;
        for (int i = 0; i < len - n; i++) { //going forward len - n == head and tail going backward n
            tail = tail.next;
            head = head.next;
        }
        tail.next = null;
        return head;
    }
}

Simply find the kth element from the tail and do rotate, notice that if the kth element is the tail, then no need to rotate.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || head.next == null)
            return head;
        //find the kth element from the tail
        ListNode h1 = head;
        for (int i = 0; i < n; i++) {
            if (h1.next != null)
                h1 = h1.next;
            else
                h1 = head;
        }
        ListNode t1 = head;
        while(h1.next != null) {
            h1 = h1.next;
            t1 = t1.next;
        }
        if (t1.next == null) // no need to rotate
            return head;
        //append the kth element to the head
        ListNode h = t1.next;
        t1.next = null;
        h1.next = head;
        return h;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s