LeetCode #24. Swap Nodes in Pairs プログラミング練習

問題：

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

LinkedListの問題が立て込んでますね。
やはりArrayとは違い、LinkedLIstはノード毎に繋がりをもっているので、
ただ隣接のノードの値を交換するのではなく、ノードの持つ繋がりを変えなければいけません。
そもそもswapとかにはあまり向いてない型なのですがデータ構造を理解するにはいい問題です。

注意すべき事:　

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

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

以下回答です。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode h = new ListNode(0);
        h.next = head;
        ListNode p = h;
        while (p.next != null && p.next.next != null) {
            ListNode temp = p;
            p = p.next;
            temp.next = p.next;
            
            ListNode temp2 = p.next.next;
            p.next.next = p;
            p.next = temp2;
        }
        return h.next;
    }
}

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

pは最初のノードnullを指しています。
p.nextは入力の最初のノード1を指しています。
while文に入ります。
ListNode temp = p;
p = p.next;
temp.next = p.next;
この文でnull->2->3->4になります。
　　　　1↗
pは1を指しています。
続いて
ListNode temp2 = p.next.next;
p.next.next = p;
p.next = temp2;
この文でnull->2->1->3->4になります。
ここで最初の二つのノードのスワップが完了しました。
注意すべきは、この時点でpは1を指しているので、p=p.nextの処理は不要です。
whileを最後まで実行すればすべてのノードがスワップされます。

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