LeetCode-in-All

24. Swap Nodes in Pairs

Medium

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]

Constraints:

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

Solution

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function swapPairs(head: ListNode | null): ListNode | null {
    if (head === null) {
        return null
    }
    const len = getLength(head)
    return reverse(head, len)
}

function getLength(curr: ListNode | null): number {
    let cnt = 0
    while (curr !== null) {
        cnt++
        curr = curr.next
    }
    return cnt
}

// Recursive function to reverse in groups
function reverse(head: ListNode | null, len: number): ListNode | null {
    // base case
    if (len < 2) {
        return head
    }
    let curr: ListNode | null = head
    let prev: ListNode | null = null
    let next: ListNode | null
    for (let i = 0; i < 2; i++) {
        // reverse linked list code
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    head.next = reverse(curr, len - 2)
    return prev
}

export { swapPairs }

This site is open source. Improve this page.