Swapping Nodes In A Linked List - Leetcode Solution

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 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 approach:

In this problem, we have to swap every two adjacent nodes in a linked list. We can solve this problem recursively by swapping the next two nodes and then recursively calling the function to swap the remaining nodes.

We consider the following cases:

• If the list is empty or has only one node, we return the head of the list. • For two nodes, we swap the nodes and return the new head of the list. • For more than two nodes, we swap the first two nodes, and then recursively call the function to swap the remaining nodes.

Step 1: Initialize a recursive function that takes the head of the list as an argument.

Step 2: If the list is empty or has only one node, return the head of the list.

Step 3: Set the next node and the next to next node of the current node and swap them.

Step 4: Recursively call the function with the next to the next node as an argument.

Step 5: Return the next node as the new head of the list.

Python Code:

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

    next_node = head.next
    head.next = self.swapPairs(next_node.next)
    next_node.next = head
    
    return next_node

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the number of nodes in the linked list. This is because we have to traverse all the nodes in the list once.

Space Complexity:

The space complexity of the above algorithm is O(n), where n is the number of nodes in the linked list. This is because we are using a recursive stack to swap the nodes.

1