Question
Formatted question description: https://leetcode.ca/all/61.html
61 Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
@tag-linkedlist
Algorithm
First traverse the original linked list to get the length n of the linked list, and then take the remainder of k to n, so that k must be less than n.
Use the fast and slow pointers to solve, the fast pointer first walks k steps, and then the two pointers go together, when the fast pointer reaches the end , The next position of the slow pointer is the head node of the new order, so that the linked list can be rotated.
Code
Java
public class Rotate_List {
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null) {
return head;
}
// k could be larger than list-length
int length = 0;
ListNode p = head;
while (p != null) {
length++;
p = p.next;
}
// avoid circle rotate
k = k % length;
if (k == 0) {
return head;
}
// two pointers, j is k behind i
ListNode i = head;
while (k > 0) {
i = i.next;
k--;
}
ListNode j = head;
while (i.next != null) { // i will stop at last node, j will stop at after-rotate end node
i = i.next;
j = j.next;
}
ListNode newHead = j.next; // @note: here, hidden assumption is "j.next != null” . eg: input: list=[1], k=0
j.next = null; // cut
i.next = head; // link
return newHead;
}
}
public class Solution_make_circle {
public ListNode rotateRight(ListNode head, int n) {
if (head == null || head.next == null || n == 0)
return head;
// compare list length with k, what if k is extremely large
ListNode ptail = head;
int count = 1;
while (ptail.next != null) {
count++;
ptail = ptail.next;
}
int cutoff = count - (n % count);
ptail.next = head; // @note: connect head tail, making it circular list
for (int i = 0; i < cutoff; i++) {
ptail = ptail.next;
}
ListNode newhead = ptail.next;
ptail.next = null;
return newhead;
}
}
}