Topic: Linked Lists in Python – Part 4: Merging, Sorting, and Advanced Interview Problems

---

In this final part of the Linked List series, we’ll tackle more advanced and practical use cases like merging sorted lists, sorting a linked list, and interview-level challenges.

---

1. Merging Two Sorted Linked Lists

def merge_sorted_lists(l1, l2):
    dummy = Node(0)
    tail = dummy

    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 or l2
    return dummy.next

---

2. Sorting a Linked List (Merge Sort – O(n log n))

def merge_sort(head):
    if not head or not head.next:
        return head

    # Split list
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    left = merge_sort(head)
    right = merge_sort(mid)

    return merge_sorted_lists(left, right)

• Attach this to your LinkedList class to sort self.head.

---

3. Removing Duplicates from a Sorted List

def remove_duplicates(self):
    current = self.head
    while current and current.next:
        if current.data == current.next.data:
            current.next = current.next.next
        else:
            current = current.next

---

4. Intersection Point of Two Linked Lists

def get_intersection_node(headA, headB):
    if not headA or not headB:
        return None

    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a  # Can be None or the intersecting node

---

5. Flatten a Multilevel Linked List

Imagine a list where each node has next and child pointers. Recursively flatten:

def flatten(node):
    if not node:
        return None

    next_node = node.next
    if node.child:
        child_tail = flatten(node.child)
        node.next = node.child
        node.child = None
        child_tail.next = flatten(next_node)
        return child_tail if child_tail.next else child_tail
    else:
        node.next = flatten(next_node)
        return node

---

Summary

• You now know how to merge, sort, and deduplicate linked lists.

• Techniques like merge sort, two-pointer traversal, and recursive flattening are essential for mastering linked lists.

• These problems are frequently asked in interviews at top tech companies.

---

Exercise

• Given two unsorted linked lists, write a function that returns a new linked list containing only the elements present in both lists (intersection), without using extra space or sets.

---

#DSA #LinkedList #MergeSort #AdvancedDSA #CodingInterview

https://t.iss.one/DataScience4