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.
Method:
Note if k % size == 0, we can just return original list
Solution:
Time: O(n) Space: O(1)
/** * Definition for singly-linked list. * class ListNode { * public int val; * public ListNode next; * ListNode(int x) { val = x; next = null; } * } */ public class Solution { public ListNode rotateRight(ListNode A, int B) { int size = 0; ListNode curr = A; while (curr != null) { size ++; curr = curr.next; } if (B >= size) { B = B % size; } if (B == 0) return A; curr = A; int target = size - B; int n = 1; while (n < target) { n ++; curr = curr.next; } ListNode newHead = curr.next; ListNode end = curr.next; curr.next = null; while (end.next != null) { end = end.next; } end.next = A; return newHead; } }