Function only outputs the last node but not the merged list + Linked List

Question

Here is my approach when merge two linked lists:

def merge(self, l1, l2):
 cur = Node() #Creating a dummy node

 while l1 and l2:
  if l1.val <= l2.val:
   cur.next = l1
   l1 = l1.next
  else:
   cur.next = l2
   l2 = l2.next

#Skipped a block here to keep it short, not related to the question

 return cur.next

But the function only returns the last node instead of merging, and when I add a pointer to it, it does the right thing:

def merge(self, l1, l2):
 cur = Node() #Creating a dummy node
 p = cur #Pointer

 while l1 and l2:
  if l1.val <= l2.val:
   p.next = l1
   l1 = l1.next
  else:
   p.next = l2
   l2 = l2.next

return cur.next

Can someone explain? I can't seem to understand the purpose of using a pointer here. Many thanks!

Answer 1

Neither of the merge is correct they extract elements till both of them are having elements what if either l1 or l2 finishes them remaining elements will be unmerged.

In the below approach we are just moving around cur.next when we return curr.next it will be the last Node since we are setting this vlaue only either through cur.next = l1 or cur.next = l2 because of this the below approach will get only last Node.

 while l1 and l2:
  if l1.val <= l2.val:
   cur.next = l1
   l1 = l1.next
  else:
   cur.next = l2
   l2 = l2.next

#Skipped a block here to keep it short, not related to the question

 return cur.next

Merge:

def merge(l1, l2):
    start = None
    curr = None

    arr = list()
    
    while l1 or l2:
        if l1:
            arr.append(l1.val)
            l1 = l1.next
        elif l2:
            arr.append(l2.val)
            l2 = l2.next
    arr = sorted(arr)
    for val in arr:
        if curr:
            curr.next = Node(val = val)
            curr = curr.next
        else:
            curr = Node(val = val)
            start = curr
    return start 

Source:

class Node:
    def __init__(self, val = None, nextN = None):
        self.next = nextN
        self.val = val 

def merge(l1, l2):
    start = None
    curr = None

    arr = list()

    while l1 or l2:
        if l1:
            arr.append(l1.val)
            l1 = l1.next
        elif l2:
            arr.append(l2.val)
            l2 = l2.next
    arr = sorted(arr)
    for val in arr:
        if curr:
            curr.next = Node(val = val)
            curr = curr.next
        else:
            curr = Node(val = val)
            start = curr
    return start 

def printLink(node):
    temp = node
    while temp!= None :
        print(temp.val, end = '-')
        temp = temp.next
    print()


node1 = Node(val = 1)
node1.next = Node(val = 3)
node2 = node1.next
node2.next = Node(val = 4)


node2 = Node(val = 1)
node2.next = Node(val = 3)
node3 = node2.next
node3.next = Node(val = 8)
node3.next.next = Node(val = 5)

printLink(node1)
printLink(node2)

printLink(merge(node1, node2))

Answer 2

The problem with both code snippets, is that in the loop you attach the node (either l1 or l2) to the same next attribute, over and over again. So each iteration overwrites the attribute value that was determined by the previous iteration.

In each iteration you need to move the reference to the next node -- the one that was just assigned to next.

The second snippet is slightly better, as it foresees that you need two references: one to remain at the dummy node, and the other one that walks forward as nodes are assigned to next attributes.

Some other remarks:

• Use more indentation. It is common practice to use 4 spaces for each indentation.
• Use descriptive variable names. If a node is a dummy node, why not call it dummy?

So:

def merge(self, l1, l2):
    dummy = Node()
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next  # This was missing!

    # Attach the remainder (either l1 or l2)
    current.next = l1 or l2

    return dummy.next