Similar Problems
Similar Problems not available
Swap Nodes In Pairs - Leetcode Solution
Companies:
LeetCode: Swap Nodes In Pairs Leetcode Solution
Difficulty: Medium
Topics: linked-list
The Swap Nodes in Pairs problem on Leetcode is a problem that requires swapping every two adjacent nodes in a linked list, and returning the modified list.
Here is a detailed solution to the problem:
First, we need to understand the structure of a singly linked list. A singly linked list is a sequence of nodes, with each node containing a value and a pointer to the next node in the list. The head node is the first node in the list, and the tail node is the last node in the list, with its pointer pointing to NULL.
The problem requires us to swap every two adjacent nodes in the linked list. In other words, if we have a linked list like this:
1 -> 2 -> 3 -> 4 -> 5
We need to modify it to:
2 -> 1 -> 4 -> 3 -> 5
To solve the problem, we can create a new linked list and swap every pair of adjacent nodes from the original linked list. This requires iterating over the original linked list and creating a new node for each swapped pair in the new linked list.
Here is the step-by-step algorithm to solve the problem:
-
Create a new empty linked list.
-
Initialize a pointer "prev" to NULL, which will track the last node in the new linked list.
-
Initialize a pointer "curr" to the head of the original linked list.
-
Iterate over the original linked list, swapping every pair of adjacent nodes.
-
For each pair of adjacent nodes (let's call them node1 and node2), swap them by updating their next pointers: a. Set node1's next pointer to node2's next pointer b. Set node2's next pointer to node1
-
Connect the swapped pair of nodes to the new linked list by updating the pointers of the nodes in the new linked list: a. If prev is not NULL, then set prev's next pointer to node2 (the second node of the swapped pair). b. Otherwise, set the head of the new linked list to node2 (the second node of the swapped pair).
-
Update prev to be node1 (the first node of the swapped pair).
-
Update curr to be the next node in the original linked list (which is node1's original next pointer).
-
Repeat steps 4-8 until we reach the end of the original linked list.
-
Return the head of the new linked list.
Here is the implementation of the solution in Python:
class ListNode: def init(self, val=0, next=None): self.val = val self.next = next
class Solution: def swapPairs(self, head: ListNode) -> ListNode: # Step 1: Create a new empty linked list dummy = ListNode(0) # Step 2: Initialize a pointer "prev" to NULL prev = dummy # Step 3: Initialize a pointer "curr" to the head of the original linked list curr = head
# Step 4: Iterate over the original linked list, swapping every pair of adjacent nodes
while curr and curr.next:
# Step 5: Swap the pair of nodes
node1 = curr
node2 = curr.next
node1.next = node2.next
node2.next = node1
# Step 6: Connect the swapped pair of nodes to the new linked list
prev.next = node2
# Step 7: Update prev to be node1
prev = node1
# Step 8: Update curr to be the next node in the original linked list
curr = node1.next
# Step 10: Return the head of the new linked list
return dummy.next
The time complexity of the solution is O(n), where n is the number of nodes in the linked list, because we make a single pass over the original linked list. The space complexity of the solution is O(1), since we use only constant extra space.
Swap Nodes In Pairs Solution Code
1