0061. Rotate List

https://leetcode.com/problems/rotate-list

Description

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

ac

/**
 * 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.
*/