DSA Interview Prep · Lesson

Merge, Split, and Find Nth from End

Merge two sorted linked lists in O(n), split a list at a midpoint using slow-fast pointers, and find the nth node from the tail.

Three Essential Linked List Patterns

This lesson covers three foundational linked-list operations that appear constantly as building blocks in harder problems: merging two sorted lists (used in merge sort and K-way merge), splitting a list at its midpoint (used in merge sort and palindrome detection), and finding the nth node from the end (used in remove-nth-from-end).

All three rely on techniques you have already seen: the dummy head node, slow-fast pointers, and careful boundary tracking.

Merging Two Sorted Lists

LeetCode 21 'Merge Two Sorted Lists': given two sorted linked lists, return a single merged sorted list. Use a dummy head and a curr tail pointer. At each step compare the heads of the two lists and attach the smaller node to curr. When one list is exhausted, attach the remainder of the other. Time: O(n+m), Space: O(1) (in-place rewiring).

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

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr  = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2  # attach remaining nodes
    return dummy.next

def build(arr):
    d = ListNode(); c = d
    for v in arr:
        c.next = ListNode(v); c = c.next
    return d.next

def to_list(h):
    r=[]
    while h: r.append(h.val); h=h.next
    return r

print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))

All lessons in this course

← Back to DSA Interview Prep