Merging two sorted linked lists is a common problem in computer science and is often encountered in various programming tasks. The task involves merging two linked lists, where each list is already sorted in ascending order, into a single sorted linked list. The resulting linked list should also be sorted in ascending order.
Algorithm to Solve
To solve this problem, we can utilise a simple algorithm that merges the two lists in a step-by-step manner. Here's a step-by-step approach to solving this problem:
1. Create a new dummy node that will serve as the head of the merged list. Initialise it with `NULL` or any other sentinel value.
2. Check if either `headA` or `headB` is `NULL`. If one of them is `NULL`, return the other list as the merged list since there is no need for merging.
3. Initialize two pointers, `currentA` and `currentB`, to the heads of the input lists `headA` and `headB`, respectively.
4. Compare the values of `currentA` and `currentB`. Take the smaller value and append it to the merged list. Move the corresponding pointer (`currentA` or `currentB`) to the next node in its list.
5. Repeat step 4 until one of the lists (`headA` or `headB`) reaches the end (i.e., the pointer becomes `NULL`).
6. Once one of the lists reaches the end, append the remaining nodes of the other list to the merged list.
7. Return the head of the merged list (excluding the dummy node).
Solution in Python
Now that we have outlined the approach, let's implement the `mergeLists` function in Python to solve the problem:
class SinglyLinkedListNode:
def __init__(self, data):
self.data = data
self.next = None
def mergeLists(headA, headB):
# Create a dummy node as the head of the merged list
dummy = SinglyLinkedListNode(None)
tail = dummy
# Check if either list is empty
if not headA:
return headB
elif not headB:
return headA
# Initialize pointers to the heads of the input lists
currentA = headA
currentB = headB
# Merge the lists
while currentA and currentB:
if currentA.data <= currentB.data:
tail.next = currentA
currentA = currentA.next
else:
tail.next = currentB
currentB = currentB.next
tail = tail.next
# Append the remaining nodes of the non-empty list
if currentA:
tail.next = currentA
elif currentB:
tail.next = currentB
return dummy.next
Now, let's test the function with the provided sample input:
# Create the linked lists from the sample input
headA = SinglyLinkedListNode(1)
headA.next = SinglyLinkedListNode(2)
headA.next.next = SinglyLinkedListNode(3)
headB = SinglyLinkedListNode(3)
headB.next = SinglyLinkedListNode(4)
# Merge the lists
merged_head = mergeLists(headA, headB)
# Print the merged list
current = merged_head
while current:
print(current.data, end=" ")
current = current.next
The output will be: `1 2 3 3 4`, which matches the expected output from the sample.
By following the outlined approach and implementing the `mergeLists` function accordingly, we can successfully merge two sorted linked lists into a single, sorted linked
list. This solution has a time complexity of O(n + m), where n and m are the lengths of the input lists, and a space complexity of O(1), as it doesn't require any additional data structures other than the dummy node.
Optimised Solution
There are a few optimizations we can apply to further improve the efficiency of the merge process:
1. Skipping unnecessary comparisons:
Since both input lists are already sorted, we can optimise the algorithm by skipping unnecessary comparisons. Instead of comparing the values of `currentA` and `currentB` at each step, we can check if the value of the current node in one list is less than or equal to the value of the current node in the other list. If this condition is not satisfied, we can directly append the remaining nodes of the other list to the merged list.
2. Avoiding unnecessary assignments:
In the previous implementation, we update the `tail` pointer at each step of the merge process. Instead of updating `tail` for every node, we can update it only when we append a new node to the merged list.
This reduces the number of assignments and improves efficiency.
Here's an optimised version of the `mergeLists` function that incorporates these optimizations:
def mergeLists(headA, headB):
# Create a dummy node as the head of the merged list
dummy = SinglyLinkedListNode(None)
tail = dummy
# Check if either list is empty
if not headA:
return headB
elif not headB:
return headA
# Initialize pointers to the heads of the input lists
currentA = headA
currentB = headB
# Merge the lists
while currentA and currentB:
if currentA.data <= currentB.data:
tail.next = currentA
currentA = currentA.next
else:
tail.next = currentB
currentB = currentB.next
tail = tail.next
# Append the remaining nodes of the non-empty list
tail.next = currentA if currentA else currentB
return dummy.next
By applying these optimizations, we reduce the number of comparisons and assignments, resulting in improved efficiency. The overall time complexity and space complexity remain the same as in the previous implementation.
Conclusion
In conclusion, merging two sorted linked lists into a single, sorted linked list is a common problem in programming. By following a step-by-step approach and implementing the `mergeLists` function, we can efficiently merge the lists while maintaining the sorted order. Additionally, by applying optimizations such as skipping unnecessary comparisons and avoiding unnecessary assignments, we can further improve the efficiency of the algorithm. This solution has a time complexity of O(n + m) and a space complexity of O(1), making it an effective approach for merging sorted linked lists in various programming tasks.