CODEWITHSUNDEEP
functionpointerslinked-listnodessingly-linked-list
notsoanonperson
notsoanonperson

Reputation: 25

Shuffle merging two linked lists with the same number of nodes

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.

Upvotes: 1

Views: 34

Answers (1)

trincot
trincot

Reputation: 350756

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.

Upvotes: 1

Related Questions