0061. Rotate List
Last updated
Last updated
https://leetcode.com/problems/rotate-list
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
**Input:** head = [1,2,3,4,5], k = 2
**Output:** [4,5,1,2,3]Example 2:
**Input:** head = [0,1,2], k = 4
**Output:** [2,0,1]Constraints:
The number of nodes in the list is in the range [0, 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 109
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
// edge case
if (head == null || head.next == null || k < 1) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = head, slow = dummy;
int step = 1;
while (fast.next != null) {
if (step >= k) slow = slow.next;
fast = fast.next;
step++;
}
// edge case
if (step == k || k % step == 0) return head;
if (step < k) {
int diff = step - k % step;
slow = dummy;
while (diff > 0) {
slow = slow.next;
diff--;
}
}
dummy.next = slow.next;
slow.next = null;
fast.next = head;
return dummy.next;
}
}
// fast, slow. fast reach tail,fast-> head, slow->null
// this question is stupid.... you don't need two pointers, it's slower and tedious..../**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
// get length
int len = 1;
ListNode r1 = head;
while (r1.next != null) {
r1 = r1.next;
len++;
}
// get cut point
ListNode r2 = dummy;
for (int i = len - k % len; i > 0; i--) {
r2 = r2.next;
}
// reconnect
r1.next = head;
dummy.next = r2.next;
r2.next = null;
return dummy.next;
}
}
/*
when k > size, k = k % size. find size, find k point, reconnect.
*/
