SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a linked list, the task is to swap every two adjacent nodes and return its head. The problem can be illustrated as:

• Input: 1 -> 2 -> 3 -> 4
• Output: 2 -> 1 -> 4 -> 3

Intuition

To solve this problem, we need to rearrange the links in the list to swap adjacent nodes. A dummy node is used to handle edge cases where the head of the list itself might be part of the pair to be swapped. The goal is to traverse the list and systematically swap every pair of adjacent nodes while maintaining the overall structure of the list.

Approach

1. Edge Cases: Handle cases where the list is empty or contains only one node. In these cases, no swapping is needed, and the list should be returned as-is.

2. Dummy Node: Use a dummy node to simplify the process of swapping nodes at the beginning of the list. The dummy node helps to manage pointers more conveniently.

3. Swapping Nodes:

   • Initialize pointers to the dummy node and the current head of the list.
   • Traverse the list in pairs, swapping the nodes by adjusting the next pointers.
   • Update the tail pointer after each swap to maintain the connection with the rest of the list.
   • Continue until all nodes are processed.

4. Return: The new head of the list is dummy.next after all pairs have been swapped.

Complexity

Time Complexity:

(O(n)), where (n) is the number of nodes in the linked list. Each node is processed once, resulting in linear time complexity.

Space Complexity:

(O(1)). The space used does not depend on the input size, as we are only using a few additional pointers.

Code

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode dummy(0);
        ListNode* tail = &dummy;
        ListNode* curr = head;

        while (curr && curr->next) {
            ListNode* temp = curr->next->next;

            tail->next = curr->next;
            curr->next->next = curr;
            curr->next = temp;

            tail = curr;
            curr = temp;
        }

        return dummy.next;
    }
};

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        dummy = ListNode(0)
        dummy.next = head
        tail = dummy
        curr = head

        while curr and curr.next:
            temp = curr.next.next

            tail.next = curr.next
            curr.next.next = curr
            curr.next = temp

            tail = curr
            curr = temp

        return dummy.next

Java

/**
 * 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 dummy = new ListNode(0);
        dummy.next = head;
        ListNode tail = dummy;
        ListNode curr = head;

        while (curr != null && curr.next != null) {
            ListNode nextPair = curr.next.next;

            tail.next = curr.next;
            curr.next.next = curr;
            curr.next = nextPair;

            tail = curr;
            curr = nextPair;
        }

        return dummy.next;
    }
}

JavaScript

var swapPairs = function(head) {
    if(!head || !head.next) return head

    let dummy = new ListNode(0)
    let tail = dummy
    let curr = head
    
    while(curr && curr.next){
        let temp = curr.next.next

        tail.next = curr.next
        curr.next.next = curr
        curr.next = temp

        tail = curr
        curr = temp
    }
    return dummy.next
};