Here is the problem statement:
Given the heads of two sorted linked lists list1andlist2, Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.
Short Overview:
In programming, specifically the data structure and algorithm domain, merging two sorted linked lists is a common, basic interview assessment exercise. This problem can be solved by using a simple linear iterative approach that selects both linked lists in a corresponding sorted order and appends them to a merged list. But in this article, we will discuss a solution that might seem unconventional but is more relatable for beginners and achieves the same result.
Structure of the singly-linked list (a node):
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
Logical Approach:
We will convert or treat the two sorted linked lists as a usual Python list, merge them by appending each value of the lists to a new list, and then sort the new list which now contains the values of both linked lists, using the built-in sort() function.
# initialise an empty list
mergedList = []
# iterate, append values of list1 to the new list until it's empty
while list1:
mergedList.append(list1.val)
list1 = list1.next
# iterate, append values of list2 to the new list until it's empty
while list2:
mergedList.append(list2.val)
list2 = list2.next
# sort the list (values of both linked lists)
mergedList.sort()
The code snippet above is a simple, traditional approach that iterates over the given input lists (list1 and list2) as long as they are not empty and adds all the values to the new, initialized empty list mergedList. With this, we've dynamically built a new list by adding all the elements of the input lists into the newly created list.
The values in mergedList are not sorted or added in any defined order, so we made use of the sort() built-in function to rearrange them in a non-decreasing order.
Now, let’s create a singly-linked list:
dummyNode = currNode = ListNode()
Here, we are creating a “dummy” node that will serve as a placeholder for the head of the linked list. It doesn’t contain any actual value or data; instead, its next pointer points to the first actual node in the list. currNode is initialized to point todummyNode, so both are instances of ListNode(). With this, we can easily append new nodes to the end of the list by updating the pointer currNode.next to point to the new node.
Concept of a sentinel node, popularly known as a dummy node:
A sentinel or dummy node is a blank template (an empty node) that helps us build the actual, real nodes. The implementation of a dummy node is commonly used to avoid handling edge cases when carrying out operations like insertion on an empty linked list. A new node can be inserted anywhere in the list, but the first node in the list has a special case because there is no previous node to link the new node to. So, by using a dummy node, we assume there is a previous node to link to. It can also be used to return the head of the linked list after certain operations, such as merging, which we will be doing in this article.
Finally, a singly-linked list using the two linked list values we merged:
for values in mergedList:
currNode.next = ListNode(values)
currNode = currNode.next
return dummyNode.next
We first loop through each value of the merged list, then create a listNode() object (a node) for each value and update the next pointer of the current node to point to a new node. We then update the currNode variable to be the newly added node. finally, the reference to the first, real node in the list is returned which is dummyNode.next.
A further breakdown of how this works:
Remember this initialization: dummyNode = currNode = ListNode(). here, we have dummyNode as a placeholder for the singly-link list head and currNode point to dummyNode. Using A, B, and C as the values in mergedList, on the first iteration, A is grabbed from mergedList, and the assignment currNod.next = ListNode(values) becomes currNode.next = ListNode(A), this assigns a node object with A as its value to currNode.next, we then assign the value of currNode.next to currNode, allowing currNode.next variable to receive another iterated value from mergedList also as a node object, Just like the value A. Now, the second value, B, is grabbed and assigned to currNode.next as a node object. We now have a linked list with the first node containing data A and a reference to the second node containing data B, A -> B. Again, the value of currNode.next (B, which is the data in the second node) is assigned to currNode as usual to allow currentNode.next variable to receive the next iterated value C from mergedList. we now have three nodes in the linked list: A -> B -> C -> None. Since there are no more nodes to add, currNode.next becomes None. Finally, the head of the linked list dummyNode.next is returned, which holds the reference to the first real node in the linked list.
In this implementation, currNode and currNode.next are used to keep track, update, traverse the linked list, and chain the nodes together. while dummyNode.next is holding a reference to the first real node in the list. So returning dummyNode.next returns the entire singly-linked list.
Here is the entire solution in one block:
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def mergeTwoLists(self, list1, list2):
mergedList = []
while list1:
mergedList.append(list1.val)
list1 = list1.next
while list2:
mergedList.append(list2.val)
list2 = list2.next
mergedList.sort()
dummyNode = currNode = ListNode()
for values in mergedList:
currNode.next = ListNode(values)
currNode = currNode.next
return dummyNode.next
Disclaimer on the efficiency of this code:
While this approach or solution works correctly, it is pertinent to note and know that it was birthed from pair discussion and, hence, is not the “most” efficient or conventionally recommended way to merge two linked lists as it involves creating a new list and sorting it, which takes extra time and space. A more efficient and optimal approach, like this one here or here without using extra space, is to directly manipulate the pointers or references of the two input linked lists to create a new merged linked list, i.e., iterating through both lists simultaneously and selecting the smallest node at each step and appending it to the merged list.
Thanks very much!
If you dedicated your time and attention to reading this article, that means you find my words compelling enough, and I must say, "Thank you."
I would greatly appreciate any feedback or contributions, as it helps me improve and produce more informative content. Feel free to reach out to me via email, LinkedIn, or Twitter. I am open to constructive criticism and eager to learn from your insights.
Reference:
Curious? Here are a few links that can give you more insights about sentinel or dummy nodes and merging singly-linked lists in Python.
merge two sorted linked lists into one
how does the dummy node get updated