# 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:

- Two pointers with one k elements ahead, so when the faster reach null, the slower one is the new head.
- Attention that k could be bigger than the length, so within the iteration, if fast reach to null, re-initialize to head.
- Mistake I made:
- Cases no need to proceed : 1. 0 node, 2. 1 node, 3. n=0
- 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