Swap Nodes
Let's explore the concept of swapping nodes in a linked list using Python. We'll start by explaining the topic thoroughly, provide an example with proper comments, and then solve a question from LeetCode that involves swapping nodes in a linked list. We'll also analyze the time and space complexity of our solution.
- Swapping Nodes in a Linked List: Swapping nodes in a linked list involves changing the positions of two nodes within the list. This operation is commonly used in various linked list problems to rearrange elements or modify the structure of the list.
The process typically includes identifying the nodes to be swapped, adjusting the pointers of the preceding and succeeding nodes, and updating the head or tail pointers if necessary. Swapping can be done by directly modifying the pointers or by swapping the values between the nodes.
- Example with Comments: Let's demonstrate the swapping of nodes in a linked list with an example. Consider the following linked list:
1 -> 2 -> 3 -> 4 -> 5
We'll swap the nodes containing the values 2 and 4, resulting in the following linked list:
1 -> 4 -> 3 -> 2 -> 5
Here's the Python code with step-by-step comments explaining each operation:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def swapNodes(head, val1, val2):
# Initialize pointers to keep track of the nodes to be swapped and their preceding nodes
node1, node2 = None, None
prev1, prev2 = None, None
# Traverse the linked list to find the nodes and their preceding nodes
curr = head
while curr:
if curr.val == val1:
node1 = curr
break
prev1 = curr
curr = curr.next
curr = head
while curr:
if curr.val == val2:
node2 = curr
break
prev2 = curr
curr = curr.next
# Handle the case when either node1 or node2 is not found
if not node1 or not node2:
return head
# Adjust the pointers to swap the nodes
if prev1:
prev1.next = node2
else:
head = node2
if prev2:
prev2.next = node1
else:
head = node1
node1.next, node2.next = node2.next, node1.next
return head
# Create the linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
node2 = head.next = ListNode(2)
node3 = node2.next = ListNode(3)
node4 = node3.next = ListNode(4)
node5 = node4.next = ListNode(5)
# Swap nodes 2 and 4
head = swapNodes(head, 2, 4)
# Print the resulting linked list: 1 -> 4 -> 3 -> 2 -> 5
curr = head
while curr:
print(curr.val, end=" -> ")
curr = curr.next
print("None")
The swapNodes
function takes the head of a linked list and the values of the nodes to be swapped as input. It traverses the linked list to find the nodes and their preceding nodes. Then, it adjusts the pointers to swap the nodes.
- Solving a LeetCode Problem: "Swap Nodes in Pairs" Now, let's solve a question from LeetCode that involves swapping nodes in a linked list.
Problem: "Swap Nodes in Pairs" Given a linked list, swap every two adjacent nodes and return its head.
You can find the problem details and constraints here: https://leetcode.com/problems/swap-nodes-in-pairs/
Here's the complete code for solving the "Swap Nodes in Pairs" problem:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def swapPairs(head):
dummy = ListNode(0)
dummy.next = head
prev = dummy
while head and head.next:
# Nodes to be swapped
first = head
second = head.next
# Swap the nodes
prev.next = second
first.next = second.next
second.next = first
# Update pointers for the next iteration
prev = first
head = first.next
return dummy.next
# Example usage
# Create the linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
node2 = head.next = ListNode(2)
node3 = node2.next = ListNode(3)
node4 = node3.next = ListNode(4)
node5 = node4.next = ListNode(5)
# Swap nodes in pairs
head = swapPairs(head)
# Print the resulting linked list: 2 -> 1 -> 4 -> 3 -> 5
curr = head
while curr:
print(curr.val, end=" -> ")
curr = curr.next
print("None")
The swapPairs
function takes the head of a linked list as input and swaps every two adjacent nodes. It uses a dummy node and three pointers to perform the swapping.
- Time and Space Complexity Analysis:
The time complexity of the
swapNodes
function is O(N), where N is the number of nodes in the linked list. This is because we need to traverse the list to find the nodes to be swapped.
The space complexity is O(1) since we are not using any additional data structures that grow with the input size.
For the "Swap Nodes in Pairs" problem, the time complexity is also O(N) since we traverse the list once. The space complexity remains O(1) as we only use a constant amount of extra space.
By understanding the concept of swapping nodes in a linked list and implementing the necessary logic, we can efficiently solve problems that involve rearranging or modifying the structure of linked lists.