Information Technology

Software Challenge: Merge Two Sorted Linked-Lists

Linked lists, a fundamental data structure, store collections of items in a sequence. Unlike arrays, where elements reside in contiguous memory locations, linked lists consist of nodes. Each node contains data and a reference to the next node in the chain. This dynamic structure excels at inserting and deleting elements at any position.

A common linked list operation involves merging two sorted lists. This article explores an efficient Python solution to achieve this task.

The Challenge: Merging Sorted Linked Lists

Imagine you have two linked lists, each containing a series of numbers arranged in ascending order. Your goal is to combine these lists while preserving the sorted order. The resulting list should contain all the elements from both originals, in ascending order.

The Solution:

Here's a step-by-step approach to solve this problem in Python:

1. Dummy Node: We'll create a dummy node, initially acting as the head of the merged list. This node serves a placeholder purpose, holding no actual data. It simplifies handling the beginning of the list during merging.

2. Tail Pointer: In addition to the dummy node, we define a tail pointer that will traverse the merged list as we add new nodes. Initially, the tail pointer will also point to the dummy node.

3. Merging Loop: The core of the solution lies in a loop that iterates as long as both original lists (list1 and list2) are not empty. Within each iteration:

   • We compare the values of the head nodes (first elements) of list1 and list2.
   • If the value in list1 is smaller, we add the list1 node to the merged list and advance the list1 pointer. This ensures the merged list remains sorted.
   • Otherwise, we add the list2 node and advance the list2 pointer.
   • In both cases, we update the tail pointer to point to the newly added node, allowing us to efficiently attach the next element during the next iteration.

4. Handling Remaining Elements: After the loop exits (when one of the lists becomes empty), we might still have elements remaining in the other list. We simply append these remaining elements to the end of the merged list using the tail pointer.

5. Return Merged List: Finally, we return the dummy.next node. Recall the dummy node was just a placeholder at the beginning. By returning dummy.next, we effectively skip the dummy node and provide the actual head of the merged sorted list.

Code in Action:

The following Python code demonstrates how to create two sample linked lists, merge them using the mergeTwoLists function, and then print the elements of the merged list.

Python

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

def mergeTwoLists(list1, list2):
  """
  Merges two sorted linked lists and returns a new sorted list.

  Args:
      list1: A sorted linked list.
      list2: A sorted linked list.

  Returns:
      A new sorted linked list containing the merged elements of list1 and list2.
  """
  dummy = ListNode(0)
  tail = dummy

  while list1 and list2:
    if list1.val < list2.val:
      tail.next = list1
      list1 = list1.next
    else:
      tail.next = list2
      list2 = list2.next
    tail = tail.next

  tail.next = list1 or list2

  return dummy.next

# Example usage
list1 = ListNode(1, ListNode(2, ListNode(4)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
mergedList = mergeTwoLists(list1, list2)

# Print the merged list
while mergedList:
  print(mergedList.val, end=" -> ")
  mergedList = mergedList.next
print("None")

Conclusion:

Merging sorted linked lists is a valuable skill for manipulating these data structures. By employing a dummy node, a tail pointer, and a carefully crafted loop, we can efficiently combine two sorted lists while maintaining the sorted order. This approach offers a clear and concise solution in Python, making it a valuable tool for your linked list endeavors.