Swap Nodes In Pairs

                                            
/**
 * 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 = new ListNode();
        dummy->next = head;
        ListNode* prev = dummy;
        
        while (prev->next && prev->next->next) {
            ListNode* first = prev->next;
            ListNode* second = prev->next->next;
            
            // Swapping
            prev->next = second;
            first->next = second->next;
            second->next = first;
            
            // Move to next pair
            prev = first;
        }
        
        return dummy->next;
    }
};

                                            
/**
 * 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 first = head;
        ListNode second = head.next;
        ListNode newHead = second;
        
        while (first != null && second != null) {
            ListNode temp = second.next;
            second.next = first;
            if (temp == null || temp.next == null) {
                first.next = temp;
                break;
            }
            first.next = temp.next;
            first = temp;
            second = temp.next;
        }
        
        return newHead;
    }
}

                                            
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head
        prev_node = dummy
        
        while head and head.next:
            first_node = head
            second_node = head.next
            
            prev_node.next = second_node
            first_node.next = second_node.next
            second_node.next = first_node
            
            prev_node = first_node
            head = first_node.next
        
        return dummy.next

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* swapPairs(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* prev = dummy;
    struct ListNode* current = head;
    
    while (current != NULL && current->next != NULL) {
        struct ListNode* firstNode = current;
        struct ListNode* secondNode = current->next;
        
        prev->next = secondNode;
        firstNode->next = secondNode->next;
        secondNode->next = firstNode;
        
        prev = firstNode;
        current = firstNode->next;
    }
    
    head = dummy->next;
    free(dummy);
    
    return head;
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode SwapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        
        while (current.next != null && current.next.next != null) {
            ListNode firstNode = current.next;
            ListNode secondNode = current.next.next;
            
            firstNode.next = secondNode.next;
            current.next = secondNode;
            current.next.next = firstNode;
            
            current = current.next.next;
        }
        
        return dummy.next;
    }
}

                                            
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if (!head || !head.next) {
        return head;
    }
    
    let dummy = new ListNode(0);
    dummy.next = head;
    let current = dummy;
    
    while (current.next && current.next.next) {
        let first = current.next;
        let second = current.next.next;
        
        first.next = second.next;
        current.next = second;
        current.next.next = first;
        
        current = current.next.next;
    }
    
    return dummy.next;
};

                                            
/**
 * 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 || !head.next) {
        return head;
    }
    
    let firstNode = head;
    let secondNode = head.next;
    
    firstNode.next = swapPairs(secondNode.next);
    secondNode.next = firstNode;
    
    return secondNode;
};

                                            
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     * @return ListNode
     */
    function swapPairs($head) {
        $dummy = new ListNode(0);
        $dummy->next = $head;
        $current = $dummy;
        
        while ($current->next != null && $current->next->next != null) {
            $first = $current->next;
            $second = $current->next->next;
            
            $first->next = $second->next;
            $current->next = $second;
            $current->next->next = $first;
            
            $current = $current->next->next; // Move to the next pair
        }
        
        return $dummy->next;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func swapPairs(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        
        let newHead = head?.next
        head?.next = swapPairs(newHead?.next)
        newHead?.next = head
        
        return newHead
    }
}

                                            
/**
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun swapPairs(head: ListNode?): ListNode? {
        if (head?.next == null) {
            return head
        }
        
        val newHead = head.next
        head.next = swapPairs(newHead?.next)
        newHead.next = head
        
        return newHead
    }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    dummy := &ListNode{Val: 0, Next: head}
    prev := dummy
    
    for prev.Next != nil && prev.Next.Next != nil {
        first := prev.Next
        second := prev.Next.Next
        
        first.Next = second.Next
        second.Next = first
        prev.Next = second
        
        prev = first
    }
    
    return dummy.Next
}

                                            
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @return {ListNode}
def swap_pairs(head)
    return head if head.nil? || head.next.nil?
    
    new_head = head.next
    current = head
    
    while !current.nil? && !current.next.nil?
        temp = current.next.next
        current.next.next = current
        current.next = temp&.next || temp
        current = temp
    end
    
    new_head
end

To solve this coding challenge, we need to create a function capable of swapping every two adjacent nodes in a linked list and returning the head of the new, modified list. The function should not alter the values within the given nodes but should modify the pointers that link the nodes to achieve the required swaps. Below is a detailed explanation of how to approach this problem and the pseudocode required to implement it.

# Explanation

Initial Checks :

First, we must handle edge cases where the linked list is either empty or contains only one node. In such cases, there's nothing to swap, so we can immediately return the head of the list.

Dummy Node :

We use a dummy node to simplify edge cases such as handling changes at the head of the list. The dummy node points to the head of the list and will make pointer manipulation cleaner and easier.

Pointer Initialization :

We use a pointer from the dummy node to start swapping nodes. This pointer,
prev_node

, helps keep track of the node previous to the pair being swapped.

Swapping Pairs in a Loop :

We iterate through the list while there are at least two nodes to be swapped (
head

and
head.next

should be non-null).
For every iteration,
first_node

points to the node currently at
head

, and
second_node

points to the node right after it (
head.next

).
By adjusting the pointers, we make
second_node

the first in the pair and
first_node

the second in the pair.
We then update
prev_node

to point to
first_node

and move
head

two steps forward for the next iteration.

Termination and Returning the Result :

Once all pairs are swapped, the modified list is accessed by returning
dummy.next

, which points to the head of the new list.

Detailed Steps in Pseudocode

Here’s the step-by-step approach:

Initialization and Edge Cases

                                            
# Create a function named swapPairs that receives the head of the linked list
function swapPairs(head):
    # If head is null or there is only one node, return head directly
    if head is null or head.next is null:
        return head

Dummy Node and Initial Pointers

                                            
    # Create a dummy node that helps with pointer manipulations, initially pointing to the head of list
    dummy = new ListNode(0)
    dummy.next = head
    
    # Initialize prev_node to dummy
    prev_node = dummy

Loop Through List for Swaps

                                            
    # Loop through the list while head and head.next are not null
    while head is not null and head.next is not null:
        # first_node is the current node pointed by head
        first_node = head
        # second_node is the next node pointed by head.next
        second_node = head.next
        
        # Re-point the previous node's next to second_node (swap start)
        prev_node.next = second_node
        # Make the first_node (currently head) point to the node after second_node
        first_node.next = second_node.next
        # Complete the swap by having second_node point (now) to first_node
        second_node.next = first_node
        
        # Move prev_node pointer two nodes ahead
        prev_node = first_node
        # Advance head pointer two nodes ahead for the next iteration
        head = first_node.next

Return Modified List

                                            
    # Return the next of dummy node which is new head of modified list
    return dummy.next

By following this detailed methodology and understanding the underlying mechanics of linked list manipulation, one can effectively solve the problem of swapping every two adjacent nodes in a linked list.