Swap Nodes In Pair

Given a singly linked list, swap every two adjacent nodes of the linked list. After the swap, return the head of the linked list.

Given a singly linked list, swap every two adjacent nodes of the linked list. After the swap, return the head of the linked list.

Note: Solve the problem without modifying the values in the list's nodes. In other words, only the nodes themselves can be changed.

Constraints

• The number of nodes in the list is in the range [0, 100].
• 0 ≤ Node.value ≤ 100

Examples

Example 1

Input: head = [9, 0, 8, 2]

Output: [0, 9, 2, 8]

Example 2

Input: head = [0, 8, 3, 1, 9, 2, 7, 0]

Output: [8, 0, 1, 3, 2, 9, 0, 7]

Solution

Manually reverse every two pairs by storing next pair information so we can connect them after reversing.

function swapPairs(head) {
    let dummy = new Node(0, head);
    let prev = dummy;
    let curr = head;

    while (curr !== null && curr.next !== null) {
        let second = curr.next;
        let nextPair = second.next;   // where the NEXT pair will begin — grab it now, before we lose it

        // Rewire this pair using nextPair instead of re-walking .next.next
        second.next = curr;
        curr.next = nextPair;
        prev.next = second;

        // Advance to the next pair
        prev = curr;
        curr = nextPair;
    }

    return dummy.next;
}

or

var swapPairs = function (head) {
    let dummy = new ListNode(0, head);
    let prev = dummy;
    let curr = head;

    function reverseK(head, k = 2) {
        let prev = null;
        let curr = head;
        let next = null;

        while (curr !== null && k > 0) {

            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            k--;
        }

        return [prev, curr];
    }

    while (curr !== null && curr.next !== null) {


        let pairStart = curr;

        let [reversedStart, nextPair] = reverseK(curr);

        prev.next = reversedStart;

        pairStart.next = nextPair;

        prev = pairStart;

        curr = nextPair;



    }
    return dummy.next;
};