Swap Nodes in Pairs

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,

Given 

1->2->3->4

, you should return the list as 

2->1->4->3

.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

給定一個連結清單，把相鄰兩個結點調換位置；傳回head

Java代碼：

1 package com.rust.cal;
 2 
 3 /**
 4  * Definition for singly-linked list.
 5  * public class ListNode {
 6  *     int val;
 7  *     ListNode next;
 8  *     ListNode(int x) { val = x; }
 9  * }
10  */
11 public class SwapNodesinPairs {
12     public static ListNode swapPairs(ListNode head) {
13         if (head == null || head.next == null) {
14             //必須先判斷head是否為null，否則會出java.lang.NullPointerException
15             //如果輸入的head == null，先判斷head.next會找不到目标
16             return head;
17         }
18         /* 針對前兩個結點 */
19         ListNode pre = head.next, later, veryFirst;
20         head.next = pre.next;
21         pre.next = head;
22         head = pre;
23         later = head.next;
24         /* 
25          * 針對後續結點
26          * 連續有2個結點，才進行換位
27          */
28         while (later.next != null && later.next.next != null) {
29             veryFirst = later;
30             pre = pre.next.next;
31             later = later.next.next;
32             pre.next = later.next;
33             later.next = pre;
34             veryFirst.next = later;
35             later = pre;
36             pre = veryFirst.next;
37         }
38         return head;
39     }
40     
41     public static void main(String args[]){
42         /*
43          * prepare data
44          */
45         ListNode head = new ListNode(1);
46         ListNode initHead = head;
47         for (int i = 2; i < 10; i++) {
48             initHead.next = new ListNode(i);
49             initHead = initHead.next;
50         }
51         
52         head = swapPairs(head);
53         /*
54          * show data
55          */
56         ListNode newHead = head;
57         while(newHead != null){
58             System.out.print(newHead.val + "  ");
59             newHead = newHead.next;
60         }
61         ListNode nothing = new ListNode(1);
62         swapPairs(nothing.next);
63     }
64 }      

輸出：

2  1  4  3  6  5  8  7  9  

這個方法是先處理前2個結點，再循環處理後續的結點。其實結點的處理方法都差不多，在LeetCode讨論區看到遞歸解法，搬運過來

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode n1 = head;
    ListNode n2 = head.next;

    n1.next = n2.next;
    n2.next = n1;

    n1.next = swapPairs(n1.next);

    return n2;
}      

利用方法開頭對head是否為null的判斷作為遞歸的條件，比第一個方法優雅很多