Poison

24. Swap Nodes in Pairs

发表于
Recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // nodeA -> nodeB -> ...
        ListNode nodeA = head, nodeB = head.next;
        nodeA.next = swapPairs(nodeB.next);
        nodeB.next = nodeA;
        return nodeB;
    }
}
Iterate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode pre = dummyHead;

        // dummyHead -> nodeA -> nodeB -> nodeC -> ...
        //    pre    -> nodeA -> nodeB -> nodeC -> ...
        while (pre.next != null) {
            ListNode nodeA = pre.next;
            ListNode nodeB = nodeA.next;
            if (nodeB == null) {
                break;
            }

            ListNode nodeC = nodeB.next;
            nodeB.next = nodeA;
            nodeA.next = nodeC;

            // dummyHead -> nodeB -> nodeA -> nodeC -> ...
            //    pre    -> nodeB
            pre.next = nodeB;
            
            // dummyHead -> nodeB -> nodeA -> nodeC -> ...
            //                        pre
            pre = nodeA;
        }

        return dummyHead.next;
    }
}
Reference

24. Swap Nodes in Pairs