Workspace

Problem workspace

3 day streakD

Merge Sort on a Linked List

MediumLinked ListsMerging & sorting

The challenge

Sort an acyclic singly linked list into nondecreasing order using top-down merge sort.

Reuse the input nodes; the recursive calls use stack space.

Example

[4, 2, 1, 3] → [1, 2, 3, 4].

Use the walkthrough below to inspect the input and each state change.

See Merge sort, step by step

Follow the pointers. Watch each link change.

4 nodes · singly linkedIDs = node identity · ∅ = null
Unsorted input: Read the inputIDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links. Node positions stay fixed while arrows change. The pointer strip and node table below give the same state in text.head4A12A21A33A4∅
CurrentResultYellow arrow: changed next link
headA1
Inspect node links
Each row is a distinct node object. D is the dummy sentinel.
NodeValueNext
A14A2
A22A3
A31A4
A43null
Step 01 / 16

Read the input

IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.

Start from the input head pointers.
View original input

A: 4 (A1) → 2 (A2) → 1 (A3) → 3 (A4); parameters: {}

Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.

Put it into code

Lists split naturally with fast/slow pointers and merge without an auxiliary array.

Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.

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


def merge(a, b):
    dummy = Node()
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a else b
    return dummy.next


def sort_list(head):
    if head is None or head.next is None:
        return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    right = slow.next
    slow.next = None
    left = sort_list(head)
    right = sort_list(right)
    return merge(left, right)

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap