Solution For Swap Nodes In Pairs
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.
Step by Step Implementation For Swap Nodes In Pairs
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode swapPairs(ListNode head) { // if head is null or there is only one node in the linked list if(head == null || head.next == null) { return head; } // we will need to keep track of the previous node // so that we can connect the swapped nodes later ListNode prev = null; // we will also need a reference to the current head // so that we can return it later ListNode currHead = head; // we will use a while loop to iterate through the linked list while(head != null && head.next != null) { // we will need to keep track of the next node // so that we do not lose track of any nodes ListNode next = head.next.next; // now we can swap the nodes head.next.next = head; head.next = next; // if this is the first swap, we need to update the currHead if(prev == null) { currHead = head.next; } // otherwise, we need to connect the previous node to the swapped nodes else { prev.next = head.next; } // finally, we need to update prev and head prev = head; head = next; } // we will return the currHead which should now be pointing to the first swapped node return currHead; } }
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def swapPairs(self, head: ListNode) -> ListNode: # if there are no nodes or only one node, return head if not head or not head.next: return head # create a new head for the list new_head = head.next # set the first node's next to the third node head.next = head.next.next # set the second node's next to the first node new_head.next = head # recursively call the function on the remaining nodes new_head.next.next = self.swapPairs(new_head.next.next) # return the new head of the list return new_head
var swapPairs = function(head) { // if the list has no nodes or only one node, return the list as is if (!head || !head.next) { return head; } // initialize pointers for current node, next node, and previous node let curr = head; let next = head.next; let prev = null; // loop through the list, swapping nodes in pairs while (curr && next) { // if this is the first node in the list, update head to point to the next node if (!prev) { head = next; } else { // otherwise, connect the previous node to the next node prev.next = next; } // swap the next node and the current node curr.next = next.next; next.next = curr; // update previous node to be the current node prev = curr; // update the current node and next node to be the next nodes in the list curr = curr.next; next = curr ? curr.next : null; } return head; };
/** * 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 == nullptr || head->next == nullptr) { return head; } ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* current = dummy; while(current->next != nullptr && current->next->next != nullptr) { ListNode* first = current->next; ListNode* second = current->next->next; current->next = second; first->next = second->next; second->next = first; current = first; } return dummy->next; } };
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode SwapPairs(ListNode head) { //if the list is empty or consists of only one node, return it if(head == null || head.next == null){ return head; } //store the first node in a temporary variable ListNode temp = head; //store the second node in a temporary variable ListNode temp2 = head.next; //set the first node to point to the third node head = temp2.next; //set the second node to point to the first node temp2.next = temp; //set the first node to point to the second node temp.next = SwapPairs(head); //return the second node return temp2; } }