24-swap-nodes-in-pairs

Problem Statement

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 the nodes themselves may be changed).

Example:

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

codeInput: head = []
Output: []

codeInput: head = [1]
Output: [1]

Approach

To solve this problem of swapping nodes in pairs, we can use an iterative approach that traverses the linked list and swaps every two adjacent nodes. Here’s a step-by-step breakdown:

Handle Edge Cases: First, check if the list is empty or has only one node. If so, return the list as is because there’s nothing to swap.
Initialize Pointers: Use three pointers:
- slow to point to the first node of the pair to be swapped.
- fast to point to the second node of the pair.
- prev to keep track of the last node of the previous pair to link it to the newly swapped nodes.
Swap Pairs Iteratively:
- Adjust pointers to swap the nodes.
- Move the slow and fast pointers to the next pair.
- Update the prev pointer to link the swapped pairs correctly.
Update the Head: After the first swap, update the head of the list to point to the second node, which becomes the new head.

Solution

/**
 * 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) {
        if (head == null || head.next == null)
            return head;

        ListNode slow = head;
        ListNode fast = slow.next;
        ListNode prev = null;

        // New head will be the second node
        head = head.next;

        while (fast != null) {
            slow.next = fast.next;
            fast.next = slow;

            if (prev != null)
                prev.next = fast;

            if (slow.next == null)
                break;

            prev = slow;
            slow = slow.next;
            fast = slow.next;
        }

        return head;
    }
}

Analysis

Time Complexity: O(N), where N is the number of nodes in the linked list. Each node is visited once during the traversal.
Space Complexity: O(1), as no additional space is used except for a few pointers.

Conclusion

This solution effectively swaps adjacent nodes in a linked list using an iterative approach with three pointers. It ensures that all pairs of nodes are swapped in a single traversal, making the solution both time and space efficient. By carefully updating pointers, the algorithm maintains the correct order of nodes while swapping them in pairs.

You can find all my solutions at Github

Thank you for reading! Stay tuned for the next article in this series, where we'll tackle another exciting LeetCode problem.

24. Swap Nodes in Pairs

Comments

LeetCode

21. Merge Two Sorted Lists

More from this blog

Designing Web APIs: Chapter 7 - Managing Change

Designing Web APIs: Chapter 6 - Scaling APIs

Designing Web APIs: Chapter 5 - Design In Practice

Designing Web APIs: Chapter 4 - Design Best Practices

Designing Web APIs: Chapter 3 - API Security

Problem Statement

Approach

Analysis

Conclusion

Command Palette

Comments

LeetCode

21. Merge Two Sorted Lists

More from this blog

Problem Statement

Approach

Analysis

Conclusion