[LeetCode] 24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]

Explanation:

Example 2:
Input: head = []
Output: []

Example 3:
Input: head = [1]
Output: [1]

Example 4:
Input: head = [1,2,3]
Output: [2,1,3]

Constraints:
The number of nodes in the list is in the range [0, 100].
0 <= Node.val <= 100

两两交换链表中的节点。

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路

我的思路是迭代。依然是给一个 dummy 节点，然后 dummy.next = head，nextStart 是第三个节点，需要交换的只是 l2 和 l2.next，l1 永远是需要 swap 的两个节点之前的那个节点，他不参与 swap。每次交换完了之后只往前挪动一个节点的距离。我画了一个示意图，这样不容易错。我参考了这个帖子。

dummy -> 1 -> 2 -> 3 -> 4
l1      l2         ns

复杂度

时间O(n)
空间O(1)

代码

Java实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // corner case
        if (head == null || head.next == null) {
            return head;
        }

        // normal case
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode l1 = dummy;
        ListNode l2 = head;
        while (l2 != null && l2.next != null) {
            ListNode nextStart = l2.next.next;            // 记住3在什么地方
            l1.next = l2.next;                            // dummy -> 2
            l2.next.next = l2;                            // 2 -> 1
            l2.next = nextStart;                        // 1 ->3
            // 此时
            // dummy -> 2 -> 1 -> 3 -> 4
            // l1            l2
            l1 = l2;                                    // l1移动到1
            l2 = l2.next;                                // l2移动到2
        }
        return dummy.next;
    }
}
/**
dummy -> 1 -> 2 -> 3 -> 4
l1       l2        ns
**/

JavaScript实现

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    // corner case
    if (head === null || head.next === null) {
        return head;
    }

    // normal case
    let dummy = new ListNode(0);
    dummy.next = head;
    let l1 = dummy;
    let l2 = head;
    while (l2 !== null && l2.next !== null) {
        let nextStart = l2.next.next;
        l1.next = l2.next;
        l2.next.next = l2;
        l2.next = nextStart;
        l1 = l2;
        l2 = l2.next;
    }
    return dummy.next;
};