Consider the problem of merging two sorted linked lists whilst keeping the order. For instance if
L1: 1->1->2->4
and
L2: 2->3->5
Then the result should be 1->1->2->2->3->4->5. In Elements of Programming Interview, the author presents the following solution in Java, which consists of running through both lists and choosing the smallest value to add to a dummy head:
public static ListNode <Integer> mergeTwoSortedList s (ListNode <Integer> LI,
ListNode <Integer> L2) { // Creates a placeholder for the result.
ListNode <Integer> dummyHead = new ListNode<>(® , null);
ListNode <Integer> current = dummyHead;
ListNode <Integer> p1 = L1 , p2 = L2 ;
while (p1 != null && p2 != null) {
if (p1.data <= p2.data) {
current.next = p1;
p1 = p1.next ;
} else {
current.next = p2 ;
p2 = p2.next ;
}
current = current.next ;
}
// Appends the remaining nodes of p1 or p2.
current.next = p1 != null ? p1 : p2 ;
return dummy head.next ;
}
The author then states that this solution is O(1) in space since it is not creating any additional nodes.
I’ve implemented a very similar solution in Python, but I noticed that there is a problem with the following (same is applicable for p2):
current.next = p1 p1 = p1.next
I noticed that, in Python, in this case, the solution won’t work for updating the value of p1 in the second line will also change the value of current.next in the line above (i.e the first line is a shallow copy), thus making the resulting list be None (equivalent to Null pointer). It is possible to have a working solution in python by replacing the first line with
current.next = NewNode(p1.val,None)
Where NewNode creates a new node with the same value as p1 and a next “pointer” pointing to None. However, this clearly will utilise O(m+n) space where m and n are the lengths of both lists.
But this made me question que whole statement inside the if blocks in the Java code. When I do current.next = p1, am I not creating a (deep) copy of the list and therefore using extra space? How come the space complexity in this case is O(1)? I understand from a more algorithmic view where the O(1) space claim comes from, but I am failing to see this materialise in the code. If p1 = p1.next does not update the value of current, there must be a difference in them, so a deep copy must be occuring, but this would mean extra space. What am I missing?
Advertisement
Answer
I don’t know where you went astray in your python implementation, but it should work fine without the current.next = NewNode(p1.val,None) change you made which creates additional nodes (and thus uses extra space). No deep copies are performed nor necessary, because the algorithm is essentially just manipulating pointers. That is, I think the main thing you’re missing is that objects are implicitly references in Java and Python (which are implicitly pointers). This means current and p1 are just two different references to nodes (they aren’t the nodes themselves).
About the block of code in question:
current.next = p1 p1 = p1.next
When you execute current.next = p1, you’re setting the next field of current to be the value of p1. Because p1 is a node, i.e. an object, and objects are references, the value of p1 is a reference to a node. So, after the first statement executes, current.next is a reference to the same node p1 refers to (there’s no deep copy).
Then, with p1 = p1.next, you’re re-defining the variable p1, which is currently a reference to a node, to be the value of p1.next: either a reference to another node or None. This second statement doesn’t change the underlying node that p1 referred to, nor does it impact the value of current.next: you’re just making p1 refer to a different node than it did previously.
Because the algorithm is only updating next fields through references to the currently existing nodes in L1 and L2 rather than creating new nodes, it is O(1). You can see a working python implementation below:
class ListNode:
def __init__(self, data, next):
self.data = data
self.next = next
def print(self):
def _print(node, seq):
seq.append(node.data)
_print(node.next, seq) if node.next else print(seq)
_print(self, [])
def mergeLists(L1, L2):
dummyHead = ListNode(None, None)
current = dummyHead
p1, p2 = L1, L2
while p1 and p2:
if p1.data <= p2.data:
current.next = p1
p1 = p1.next
else:
current.next = p2
p2 = p2.next
current = current.next
current.next = p1 if p1 else p2
return dummyHead.next
L1 = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, None)))))
L1.print() # [1, 2, 3, 4, 5]
L2 = ListNode(3, ListNode(4, ListNode(6, None)))
L2.print() # [3, 4, 6]
merged = mergeLists(L1, L2)
merged.print() # [1, 2, 3, 3, 4, 4, 5, 6]