LeetCode #25. Reverse Nodes in k-Group プログラミング練習

問題：

難易度:　hard
入力:　ListNode
目的: 隣接のn個のノードをすべてスワップして返せ
出力:　ListNode

前回の♯23問の延長問題です。
23問目は隣接二つのノードをスワップする問題でしたが、
今回の問題は隣接ｎ個のノードをスワップしなければなりません。
しかし基本的な考え方は同じですので、ノード間の位置関係を変えていけばいいのです。

注意すべき事:　

• Extra SpaceはO(1)に抑える

• 各ノードが持つ値をスワップするのではなく関係を変換しましょう。

• ｎがノード数を上回る時はそのまま返す

以下回答です。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k<2) return head;
        ListNode h = new ListNode(0);
        h.next = head;
        ListNode t = h; //tail
        ListNode p = h; //prev
        int count;
        while (true) {
            count = k;
            while (t != null && count > 0) {
                t = t.next;
                count--;
            }
            if (t == null) break;
            head = p.next;
            while (p.next != t) {
                ListNode temp = p.next;
                p.next = temp.next;
                temp.next=t.next;
                t.next=temp;
            }
            p = head;
            t = head;
        }
        
        return h.next;
    }
}

whileで前から一つずつスワップして行くアルゴリズムです。
例で説明しますと:
入力:
1->2->3->4　k = 2

pは最初のノードnullを指しています。
p.nextは入力の最初のノード1を指しています。
tailはpからn番目のノードを指しています。
while文に入ります。
ListNode temp = p.next;
p.next = temp.next;
temp.next=t.next;
t.next=temp;
この文でnull->2->1->3->4になります。
while文に入る前にhead = p.nextの処理をしているので
whileのあとにp,tをheadに指せば次のノードに移ってくれます。
whileを最後まで実行すればすべてのノードがスワップされます。

今日は以上。
よいプログラミング生活を！