Swap Nodes in Pairs

Problem

源地址: 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

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

Input: head = []
Output: []

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

Solution

1. 递归方式

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

2. 生成新链表

   var swapPairs = function (head) {
    if (!head) {
        return null;
    }
    let res = {
        val: head.val,
        next: null
    };
    let tail = res;
    let next = head.next;
    let swap = true
    while(next) {
        if (swap) {
            const tailVal = tail.val;
            const tailNext = tail.next;
            tail.val = next.val;
            tail.next = {
                val: tailVal,
                next: tailNext
            }
        } else {
            tail.next = {
                val: next.val,
                next: null
            }
        }
   
        tail = tail.next;
        next = next.next;
        swap = !swap;
    }
   
    return res;
   };