摘要：三指針法復雜度時間空間思路基本的操作鏈表，見注釋。注意使用頭節點方便操作頭節點。翻轉后，開頭節點就成了最后一個節點。

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.

時間 O(N) 空間 O(1)

基本的操作鏈表，見line注釋。注意使用dummy頭節點方便操作頭節點。

public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // curr是待交換的兩個節點前面那個節點
        ListNode curr = dummy;
        while(curr != null && curr.next != null && curr.next.next != null){
            ListNode third = curr.next.next.next;
            ListNode second = curr.next.next;
            ListNode first = curr.next;
            // 把第二個節點的next置為第一個節點
            second.next = first;
            // 把當前節點的next置為第二個節點
            curr.next = second;
            // 把第一個節點的next置為第三個節點
            first.next = third;
            // 將當前節點置為第一個節點，繼續下一輪交換（此時first實際已經是第二個節點了）
            curr = first;
        }
        return dummy.next;
    }
}

不想用那么多指針？

public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;
        while(curr != null && curr.next != null && curr.next.next != null){
            ListNode tmp = curr.next.next.next; // tmp - 3
            curr.next.next.next = curr.next;    // 3 - 1
            curr.next = curr.next.next;         // 1 - 2
            curr.next.next.next = tmp;          // 3 - tmp
            curr = curr.next.next;              // 0 - 2
        }
        return dummy.next;
    }
}

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example, Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

時間 O(N) 空間 O(1)

其實就是每K個節點執行一次反轉鏈表，不過這里有幾點要注意：

如果剩余節點不足K個則不執行反轉，所以要先判斷是否可以反轉

為了拼接這個反轉過后的鏈表，我們需要類似Reverse Linked List II一樣的操作，即記錄下該段鏈表的開頭節點，這個開頭節點的前一個節點，該鏈表的最后一個節點，和這最后一個節點的下一個節點。翻轉后，開頭節點就成了最后一個節點。

拆分成子函數，清晰易懂

K等于1的時候直接返回原鏈表

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;
        while(curr != null && curr.next != null && curr.next.next != null){
            // 檢測是否有足夠節點供反轉，不足直接退出
            if(!hasEnoughNodes(curr.next, k)) break;
            // 記錄下第一個節點，反轉后成為最后一個節點
            ListNode last = curr.next;
            // 從這第一個節點開始反轉K個節點
            ListNode[] nodes = reverseK(last, k);
            // 將第0個節點的next接上新鏈表的頭節點
            curr.next = nodes[0];
            // 將新鏈表的尾節點的后一個節點置為后一段鏈表的頭節點
            last.next = nodes[1];
            // 準備反轉下一段鏈表
            curr = last;
        }
        return dummy.next;
    }
    
    private boolean hasEnoughNodes(ListNode runner, int k){
        int remains = 0;
        while(runner != null && remains < k){
            remains++;
            runner = runner.next;
        }
        if(remains < k) return false;
        return true;
    }
    
    private ListNode[] reverseK(ListNode p1, int k){
        ListNode p2 = p1.next;
        // 反轉K個節點
        while(p2 != null && k > 1){
            ListNode tmp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = tmp;
            k--;
        }
        // 返回值第一個是新的鏈表頭節點，第二個是下一段鏈表的頭節點
        ListNode[] res = {p1, p2};
        return res;
    } 
}