61. Rotate List - Medium

前往題目

想法

• 找到middle的時候也順便知道這個list有多長，這樣就能算出是哪幾個要接到前面去，或甚至連動都不用動直接回傳
• 當k=list的長度時候就不用動，剛好一循環

思路

大致上自己想出來了，可惜為了存middle讓code變得複雜，但實際上根本不用middle

1. 找到尾巴node和list的長度
2. 然後根據長度就可以算出新的尾巴在哪裡
3. 重新拼接就可以了

Code

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        ListNode tail = head;
        int length = 1;
        // Find tail and the length of the list
        while (tail.next != null) {
            tail = tail.next;
            ++length;
        }

        // Eliminate unecessary k
        k %= length;

        if (k == 0) return head;

        ListNode curNode = head;

        // Find new tail
        for (int i = 0; i < (length - k - 1); ++i) {
            curNode = curNode.next;
        }

        ListNode newHead = curNode.next;
        // Update new tail
        curNode.next = null;
        // Update old tail
        tail.next = head;

        return newHead;
    }
}

2024/10/12

• 想得太複雜了，還反轉了，其實只要簡單的在關鍵點轉換一下指針就好