LeetCode Problem

Problem Description

Given a linked list, swap every two adjacent nodes and return its head.

Examples

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

Constraints

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

Follow-up

Approach to Solve

Use a dummy node to simplify the process of swapping pairs.

Code Implementation

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        current = dummy
        while current.next and current.next.next:
            first = current.next
            second = current.next.next
            first.next = second.next
            second.next = first
            current.next = second
            current = first
        return dummy.next

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        while (current.next != null && current.next.next != null) {
            ListNode first = current.next;
            ListNode second = current.next.next;
            first.next = second.next;
            second.next = first;
            current.next = second;
            current = first;
        }
        return dummy.next;
    }

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* current = dummy;
        while (current->next && current->next->next) {
            ListNode* first = current->next;
            ListNode* second = current->next->next;
            first->next = second->next;
            second->next = first;
            current->next = second;
            current = first;
        }
        return dummy->next;
    }

Explanation

This solution uses a dummy node to simplify the process of swapping pairs. Here's a detailed explanation of the algorithm:

Create a dummy node: We start by creating a dummy node with a value of 0 and set its next pointer to the head of the input list. This helps handle edge cases, such as when the list has only one node or is empty.
Initialize a current pointer: We use a 'current' pointer to keep track of our current position in the list.
Iterate through the list: We continue this process while the current node has a next node and the next node has a next node. This ensures we can swap pairs of nodes.
Swap the nodes: At each step, we swap the current pair of nodes:
- Store the first node in the pair.
- Store the second node in the pair.
- Update the first node's next pointer to point to the node after the second node.
- Update the second node's next pointer to point to the first node.
- Update the current node's next pointer to point to the second node.
- Move the current pointer to the first node (which is now the second node in the pair).
Return the result: After the loop, we return the next node of the dummy node, which is the head of our modified list.

This approach is efficient because:

It only requires one pass through the list, resulting in a time complexity of O(n).
It uses constant extra space (O(1)) as we're only creating one dummy node.
It handles all edge cases smoothly, including when the list has an odd number of nodes or is empty.

The dummy node technique is particularly useful here as it simplifies the process of swapping nodes, especially when dealing with the first pair of nodes.

Time Complexity: O(n), where n is the number of nodes in the list. Space Complexity: O(1), as we only use a constant amount of extra space for the dummy node and pointers.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

LeetSolved

Swap Nodes in Pairs