Merg-Sort 2 Linked Lists

Question

I am new to data structures and algorithms, and I got this question about merging 2 linked lists and making sure they are sorted. Since I am new, I don't really know much strategies and this is how I am trying to implement it. Can anyone point out what is going wrong and how I should tackle this question? Thanks in advance.

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

def merge_lists(head_1, head_2):
  tail_1 = head_1
  tail_2 = head_2
  tail_to_use = tail_2 if tail_1.val > tail_2.val else tail_1 # 5
  current_h1 = head_1
  current_h2 = head_2
  while current_h1 is not None and current_h2 is not None:
    if current_h1.val < current_h2.val and current_h1.val != tail_to_use.val:
      tail_to_use.next = current_h2
      current_h1 = current_h1.next
    elif current_h2.val < current_h1.val and current_h2.val != tail_to_use.val:
      tail_to_use.next = current_h2
      current_h2 = current_h2.next
    tail_to_use = tail_to_use.next
  if current_h1 is not None:
    tail_to_use.next = current_h1
  if current_h2 is not None:
    tail_to_use.next = current_h2
  return head_1

This is one of the test cases I am trying to get to work

a = Node(5)
b = Node(7)
c = Node(10)
d = Node(12)
e = Node(20)
f = Node(28)
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
# 5 -> 7 -> 10 -> 12 -> 20 -> 28

q = Node(6)
r = Node(8)
s = Node(9)
t = Node(25)
q.next = r
r.next = s
s.next = t
# 6 -> 8 -> 9 -> 25

print(merge_lists(a, q))

Answer 1

My solution uses the merging method of Merge Sort.

Firstly it makes two list containing all the noded from the sequences. Than the lowest value node is selected and poped from the list. After that the algorithm goes though the lists and compares the first elements and adds the lower value node to the output sequence and removes it from the list, that is done until both of the lists are empty.

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

def merge_lists(head_1, head_2):
    list1 = [head_1]
    i = head_1
    while i is not None:
        if i.next is not None:
            list1.append(i.next)
        i = i.next
    list2 = [head_2]
    i = head_2
    while i is not None:
        if i.next is not None:
            list2.append(i.next)
        i = i.next
    
    print(list1, list2)
    head = list1[0] if list1[0].val <= list2[0].val else list2[0]
    list1.pop(0) if list1[0].val <= list2[0].val else list2.pop(0)
    currentNode = head

    while len(list1) or len(list2):
        if not len(list1):
            currentNode.next = list2[0]
            currentNode = list2[0]
            list2.pop(0)
        elif not len(list2):
            currentNode.next = list1[0]
            currentNode = list1[0]
            list1.pop(0)
        elif list1[0].val <= list2[0].val:
            currentNode.next = list1[0]
            currentNode = list1[0]
            list1.pop(0)
        else:
            currentNode.next = list2[0]
            currentNode = list2[0]
            list2.pop(0)
    return head

Answer 2

There are several issues:

• The loop may keep iterating infinitely if neither the if condition nor the elif condition is true. In that case current_h1 and current_h2 remain the same. This should never happen: in each iteration you should be sure to make some progress, and so there should be an else (not an elif) that catches all other cases.

• Related: there should not be a reason to compare a value with tail_to_use.val. It should not be a condition. At first, I did not understand what your thinking was here, but then I realised you wanted to avoid to link back to the same node in the first iteration. There are two ways to do this right:

  1. Either advance the relevant head reference to the next before the loop starts, so that tail_to_use is no longer a node whose value is compared inside the loop, or
  2. Don't perform any logic before the loop, and start with tail_to_use as None, and deal with that state inside the loop.

• The statement return head_1 will be wrong when head_2 has a value that is less than the value in head_1. In that case it should be return head_2. I would define a variable head that will take the right one (head_1 or head_2) and is returned at the end.

• When doing print(merge_lists(a, q)) you must be sure to define how a list should be printed. You need to have some logic that defines the output. For that purpose you could define a __repr__ method on your class.

Not really a problem, but:

• You can save some variables by using head_1 and head_2 to move along the lists, instead of using new current_* variables.

• The to_use suffix in the name tail_to_use seems not to serve much. Just call it tail.

Here is a corrected version:

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

    def __repr__(self):
        return str(self.val) + " -> " + str(self.next)


def merge_lists(head_1, head_2):
    head = None
    tail = None
    while head_1 is not None and head_2 is not None:
        if head_1.val < head_2.val:
            next_node = head_1
            head_1 = head_1.next
        else:
            next_node = head_2
            head_2 = head_2.next
        if head is None:
            head = next_node
        else:
            tail.next = next_node
        tail = next_node
    if head_1 is not None:
        tail.next = head_1
    else:
        tail.next = head_2
    return head