grid47 Exploring patterns and algorithms
Nov 4, 2024
5 min read
Solution to LeetCode 24: Swap Nodes in Pairs Problem
You are given the head of a singly linked list. Your task is to swap every two adjacent nodes in the list and return its head. The nodes themselves should be swapped, not just the values.
Problem
Approach
Steps
Complexity
Input: The input consists of the head of a singly linked list, where each node has a `val` representing its value.
Example: Input: head = [1, 2, 3, 4]
Constraints:
• 0 <= Node.val <= 100
• The number of nodes in the list is between 0 and 100.
Output: Return the head of the modified linked list where every two adjacent nodes have been swapped.
Example: Output: [2, 1, 4, 3]
Constraints:
Goal: The goal is to swap every two adjacent nodes while maintaining the rest of the list unchanged.
Steps:
• 1. Traverse the list with two pointers.
• 2. For each pair of adjacent nodes, swap their positions.
• 3. Ensure the swapped pairs maintain the linkage to the rest of the list.
Goal: The algorithm should efficiently handle up to 100 nodes and should not modify the values of the nodes, only the structure of the list.
Steps:
• The list may be empty or contain only one node.
Assumptions:
• The input list will always have at least zero nodes.
• Input: Input: head = [1, 2, 3, 4]
• Explanation: In this example, after swapping every two adjacent nodes, the list becomes [2, 1, 4, 3]. The first two nodes are swapped and the next pair is also swapped.
• Input: Input: head = [1]
• Explanation: In this case, there is only one node, so no swap is possible. The output will be the same single node list: [1].
• Input: Input: head = []
• Explanation: If the input list is empty, the output should also be empty.
Approach: To solve this problem, we need to traverse the list and swap every two adjacent nodes while ensuring the list structure is preserved.
Observations:
• This problem requires adjusting the pointers of adjacent nodes without changing their values.
• We can perform this in one pass over the list while keeping track of the previous and next nodes to ensure the linkage is correct after each swap.
Steps:
• 1. Check if the list is empty or has only one node. If true, return the list as is.
• 2. Initialize pointers for the previous, current, and next nodes.
• 3. Swap each adjacent pair of nodes.
• 4. Ensure proper linkage after each swap and continue until the end of the list.
Empty Inputs:
• If the input is an empty list, return an empty list.
Large Inputs:
• The solution should work efficiently for lists with up to 100 nodes.
Special Values:
• If the list contains only one node, no swap is needed and the same list should be returned.
Constraints:
• The solution must preserve the list's structure and ensure no values are modified.
This line declares a function named 'swapPairs' that takes a pointer to the head of a linked list as input and returns a pointer to the head of the modified linked list.
2 : Base Case
if(head ==NULL|| head->next ==NULL) return head;
This line checks if the list is empty or has only one node. In these cases, no swapping is needed, and the original head is returned.
This line initializes four pointers: 'cur' to the current node, 'nxt' to the next node, 'ret' to the new head (which will be the second node), and 'prv' to the previous node (initially NULL).
4 : Loop Iteration
while(cur !=NULL&& nxt !=NULL) {
This line starts a loop that continues as long as both 'cur' and 'nxt' are not NULL.
5 : Conditional Update
if(prv !=NULL) prv->next = nxt;
If there's a previous node 'prv', its 'next' pointer is updated to point to the current 'nxt' node.
6 : Pointer Update
prv = cur;
The 'prv' pointer is updated to point to the current 'cur' node.
7 : Node Manipulation
cur->next = nxt->next;
The 'next' pointer of the current node 'cur' is updated to point to the node after 'nxt'.
8 : Node Manipulation
nxt->next = cur;
The 'next' pointer of the 'nxt' node is updated to point to the current 'cur' node, effectively swapping the two nodes.
9 : Pointer Update
cur = cur->next;
The 'cur' pointer is moved to the next node, which is the original 'nxt' node after the swap.
10 : Pointer Update
if(cur !=NULL) nxt = cur->next;
If 'cur' is not NULL, the 'nxt' pointer is updated to point to the next node after 'cur'.
11 : Return
return ret;
After the loop, the function returns the new head of the linked list, which is stored in the 'ret' pointer.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Since we process each node once, the time complexity is linear, where n is the number of nodes in the list.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant since we are only using a few extra pointers for traversal and swapping.
