I have two functions for merging two linked lists assuming they have the same number of elements
The first one:
def shuffle_merge(self, l1,l2):
node1 = l1.head
node2 = l2.head
if not node1 and not node2:
return
self.head = node1
self.head.next = node2
temp = self.head.next
t1 = node1.next
t2 = node2.next
while t1 and t2:
temp.next = t1
temp = temp.next
t1 = t1.next
temp.next = t2
temp = temp.next
t2= t2.next`
And the second function:
def shuffle_merge(self, list1, list2):
if list1.head is None and list2.head is None:
return
self.head=list1.head
curr1=list1.head.next
self.head.next=list2.head
curr2=list2.head.next
new=self.head.next
while curr1 and curr2:
new.next=curr1
new=new.next
curr1=curr1.next
new.next=curr2
new=new.next
curr2=curr2.next
Now the second one seems to work as expected but the first one doesn't for example, merging the lists 3->2->5->8->9 and 6->9->4->8->4 gives me the output 3->6->4. But why? I think it might be related to how the pointers work but I don't understand it.
The problem in the first version is in this section:
self.head = node1
self.head.next = node2
temp = self.head.next
t1 = node1.next
The assignment to self.head.next is an assignment to node1.next, so when you do t1 = node1.next it is not the intended node reference.
Let's visualise it with two lists that have three nodes. Before the above quoted statements are executed, we have this:
node1
│
┌─┴─────────┐ ┌───────────┐ ┌───────────┐
│ value: 3 │ │ val: 2 │ │ val: 5 │
│ next: ────────┤ next: ────────┤ next: None│
└───────────┘ └───────────┘ └───────────┘
self
┌─┴─────────┐
│ head: None│
└───────────┘
┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 6 │ │ val: 9 │ │ val: 4 │
│ next: ────────┤ next: ────────┤ next: None│
└─┬─────────┘ └───────────┘ └───────────┘
│
node2
After the first two statements have executed, we have this:
node1
│
┌─┴─────────┐ ┌───────────┐ ┌───────────┐
│ value: 3 │ │ val: 2 │ │ val: 5 │
┌─┤ next: ┐ │ │ next: ────────┤ next: None│
│ └───────│───┘ └───────────┘ └───────────┘
self │ │
┌─┴─────│───┐ │
│ head: ┘ │ │
└───────────┘ │
┌─────────┘
│ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ │ value: 6 │ │ val: 9 │ │ val: 4 │
└─┤ next: ────────┤ next: ────────┤ next: None│
└─┬─────────┘ └───────────┘ └───────────┘
│
node2
... and you will notice how the node with value 2 has been orphaned: it is no longer reachable. When the last two statements are executed, t1 is referencing the wrong node:
node1
│
┌─┴─────────┐ ┌───────────┐ ┌───────────┐
│ value: 3 │ │ val: 2 │ │ val: 5 │
┌─┤ next: ┐ │ │ next: ────────┤ next: None│
│ └───────│───┘ └───────────┘ └───────────┘
self │ │
┌─┴─────│───┐ │
│ head: ┘ │ │
└───────────┘ │
┌─────────┘
│ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ │ value: 6 │ │ val: 9 │ │ val: 4 │
└─┤ next: ────────┤ next: ────────┤ next: None│
└─┬─────┬──┬┘ └───────────┘ └───────────┘
│ │ │
node2 t1 temp
To fix this, place the assignment to t1 before the statement that assigns to self.head.next and then you get:
node1 t1
│ │
┌─┴─────────┐ ┌─┴─────────┐ ┌───────────┐
│ value: 3 │ │ val: 2 │ │ val: 5 │
┌─┤ next: ┐ │ │ next: ────────┤ next: None│
│ └───────│───┘ └───────────┘ └───────────┘
self │ │
┌─┴─────│───┐ │
│ head: ┘ │ │
└───────────┘ │
┌─────────┘
│ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ │ value: 6 │ │ val: 9 │ │ val: 4 │
└─┤ next: ────────┤ next: ────────┤ next: None│
└─┬────────┬┘ └───────────┘ └───────────┘
│ │
node2 temp
Hope this clarifies it.