Leetcode–Rotate List

The Problem:

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.

Notes:

  1. Two pointers with one k elements ahead, so when the faster reach null, the slower one is the new head.
  2. Attention that k could be bigger than the length, so within the iteration, if fast reach to null, re-initialize to head.
  3. Mistake I made:
    1. Cases no need to proceed : 1. 0 node, 2. 1 node, 3. n=0
    2. After the while loop, if fast reach the end, means n is the length of list, just return the original head.

Java Solution:

/**
 * 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) {
        //--!!!---cases no need to proceed: 0 node; 1 node; n=0
        if(head==null || head.next == null || n==0) return head;
        ListNode fast = head;
        while(n>0){
            if(fast == null)//---n could be bigger than length
                fast = head;
            fast = fast.next;
            n--;
        }
        if(fast == null) // --!!! n is the length of list, just the same after rotation
            return head;
        ListNode slow = head;
        while(fast!= null && fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next = head;
        return newHead;
    }
}
Advertisements

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