This code merges two sorted linked lists into a single...

February 4, 2025 at 04:38 PM

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

def merge_two_sorted_lists(l1, l2):
    dummy = ListNode()  # Dummy node to simplify merging
    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

    current.next = l1 if l1 else l2  # Attach remaining nodes

    return dummy.next  # Return merged list starting from dummy.next

# Example usage
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("None")

# Creating two sorted linked lists
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))

merged_head = merge_two_sorted_lists(l1, l2)
print_list(merged_head)  # Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None

This code merges two sorted linked lists into a single sorted linked list. Here is what each part of the code does:

ListNode class:
- It defines the structure of a node in a singly linked list. Each node contains a value (val) and a pointer (next) to the next node.
- The __init__ method initializes a node with a given value (val, default is 0) and a link to the next node (next, default is None).
merge_two_sorted_lists(l1, l2) function:
- This function takes two sorted linked lists (l1 and l2) as input and merges them into a single sorted linked list.
- A dummy node (dummy) is created to simplify the merging process, and a current pointer is used to build the merged list.
- The while loop iterates as long as both l1 and l2 are not None. For each iteration:
  - Compare the current node values of l1 and l2.
  - Append the smaller node to the merged list by setting current.next to the smaller node.
  - Advance the pointer (l1 or l2) for the list from which the smaller node was taken.
  - Move the current pointer to its next position to continue building the merged list.
- After the loop, any remaining nodes in either l1 or l2 are appended to the end of the merged list using current.next = l1 if l1 else l2.
- Finally, the function returns dummy.next. The dummy node itself is only a placeholder, and the merged linked list starts from dummy.next.
print_list function:
- This is a helper function to print the contents of a linked list in a human-readable format. It iterates through the list, printing each node's value followed by an arrow (->), and terminates with "None".
Example Usage:
- Two sorted linked lists (l1 and l2) are created:
  - l1: 1 -> 2 -> 4
  - l2: 1 -> 3 -> 4
- The merge_two_sorted_lists function is called to merge them:
  - It produces the merged list: 1 -> 1 -> 2 -> 3 -> 4 -> 4.
- The print_list function is used to print the merged list.

Overall, the code merges two sorted linked lists into a single sorted list and demonstrates this with an example.

Generate your own explanations

Download our vscode extension

Read other generated explanations

Built by @thebuilderjr