24. Swap Nodes in Pairs

Leetcode

https://leetcode.com/problems/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]

Example 2:

Input: head = []
Output: []

Example 3:

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

解答

• 方法一

Recursive Approach

var swapPairs = function(head) {
    if (!head || !head.next) return head;    
    
    let firstNode = head;
    let secondNode = head.next;
    
    firstNode.next = swapPairs(secondNode.next);
    secondNode.next = firstNode;
       
    return secondNode;
};

Runtime: 101 ms, faster than 15.42% of JavaScript online submissions for Swap Nodes in Pairs.

Memory Usage: 38.4 MB, less than 96.40% of JavaScript online submissions for Swap Nodes in Pairs.

• 方法二

Iterative Approach

var swapPairs = function(head) {
    if (!head || !head.next) return head;    
    
    // 回傳第二個 node 起頭的 linked list
    let beginNode = head.next;
    let prevNode = new ListNode(-1);
    while(head && head.next) {
        let firstNode = head;
        let secondNode = head.next;

        // Swapping        
        prevNode.next = secondNode;
        firstNode.next = secondNode.next;
        secondNode.next = firstNode;
        
        // 儲存這一輪的 firstNode 以讓下一輪指到正確的 secondNode (line 12)
        prevNode = firstNode;
        // 讓 head 跳兩個 node
        head = firstNode.next;
    }
       
    return beginNode;
};

Runtime: 68 ms, faster than 91.84% of JavaScript online submissions for Swap Nodes in Pairs.

Memory Usage: 39.1 MB, less than 46.13% of JavaScript online submissions for Swap Nodes in Pairs.