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

基本的操作鏈表，見(jiàn)line注釋。注意使用dummy頭節(jié)點(diǎn)方便操作頭節(jié)點(diǎn)。

public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // curr是待交換的兩個(gè)節(jié)點(diǎn)前面那個(gè)節(jié)點(diǎn)
        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;
            // 把第二個(gè)節(jié)點(diǎn)的next置為第一個(gè)節(jié)點(diǎn)
            second.next = first;
            // 把當(dāng)前節(jié)點(diǎn)的next置為第二個(gè)節(jié)點(diǎn)
            curr.next = second;
            // 把第一個(gè)節(jié)點(diǎn)的next置為第三個(gè)節(jié)點(diǎn)
            first.next = third;
            // 將當(dāng)前節(jié)點(diǎn)置為第一個(gè)節(jié)點(diǎn)，繼續(xù)下一輪交換（此時(shí)first實(shí)際已經(jīng)是第二個(gè)節(jié)點(diǎn)了）
            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

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

其實(shí)就是每K個(gè)節(jié)點(diǎn)執(zhí)行一次反轉(zhuǎn)鏈表，不過(guò)這里有幾點(diǎn)要注意：

如果剩余節(jié)點(diǎn)不足K個(gè)則不執(zhí)行反轉(zhuǎn)，所以要先判斷是否可以反轉(zhuǎn)

為了拼接這個(gè)反轉(zhuǎn)過(guò)后的鏈表，我們需要類似Reverse Linked List II一樣的操作，即記錄下該段鏈表的開頭節(jié)點(diǎn)，這個(gè)開頭節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，該鏈表的最后一個(gè)節(jié)點(diǎn)，和這最后一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。翻轉(zhuǎn)后，開頭節(jié)點(diǎn)就成了最后一個(gè)節(jié)點(diǎn)。

拆分成子函數(shù)，清晰易懂

K等于1的時(shí)候直接返回原鏈表

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){
            // 檢測(cè)是否有足夠節(jié)點(diǎn)供反轉(zhuǎn)，不足直接退出
            if(!hasEnoughNodes(curr.next, k)) break;
            // 記錄下第一個(gè)節(jié)點(diǎn)，反轉(zhuǎn)后成為最后一個(gè)節(jié)點(diǎn)
            ListNode last = curr.next;
            // 從這第一個(gè)節(jié)點(diǎn)開始反轉(zhuǎn)K個(gè)節(jié)點(diǎn)
            ListNode[] nodes = reverseK(last, k);
            // 將第0個(gè)節(jié)點(diǎn)的next接上新鏈表的頭節(jié)點(diǎn)
            curr.next = nodes[0];
            // 將新鏈表的尾節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)置為后一段鏈表的頭節(jié)點(diǎn)
            last.next = nodes[1];
            // 準(zhǔn)備反轉(zhuǎn)下一段鏈表
            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;
        // 反轉(zhuǎn)K個(gè)節(jié)點(diǎn)
        while(p2 != null && k > 1){
            ListNode tmp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = tmp;
            k--;
        }
        // 返回值第一個(gè)是新的鏈表頭節(jié)點(diǎn)，第二個(gè)是下一段鏈表的頭節(jié)點(diǎn)
        ListNode[] res = {p1, p2};
        return res;
    } 
}