Merge two lists and remove the nth node from the end in Python

Why it matters

Both problems are classic interview questions, and they teach two habits that make linked-list code shorter and safer. The first habit is the dummy node, a placeholder placed in front of the real head. The second is the fixed gap, two pointers kept a set distance apart, which lets you find a node from the end of a list without counting. Merging is also the core step of merge sort, so it appears again in sorting problems. By the end of this lesson you will be able to merge, remove by position from the end, remove by value and find where two lists share nodes.

The problem with the first node

Lessons 1 to 3 kept seeing the same special case. Adding at the front, deleting the head and inserting before the head all need their own code, because the head has no node in front of it. A function that works for every other node fails on the first one. That is annoying, and it is also a common source of bugs, because the special case is easy to forget.

A dummy node removes the special case. It is an extra node that you place in front of the real head, and it holds no meaningful value. Its next link points at the real head. Now every real node has a node in front of it, so the code that edits the middle of a list works on the first node too. When the work is done, you return dummy.next, which is the real head, even if the old head was removed.

Think of a bookmark placed in front of the first page of a book. You can tear out the first page of the book, and the bookmark still tells you where the book starts. The bookmark never moves, and it always has a page after it.

The difference is easiest to see in code. Here is removal of a value without a dummy node:

def remove_no_dummy(head, target):
    while head is not None and head.val == target:
        head = head.next                # special case: the head itself
    if head is None:
        return None
    cur = head
    while cur.next is not None:
        if cur.next.val == target:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return head

The first loop exists only to handle the head. Now the same function with a dummy node:

def remove_with_dummy(head, target):
    dummy = ListNode(0)
    dummy.next = head                   # the real head now has a node in front of it
    cur = dummy
    while cur.next is not None:
        if cur.next.val == target:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return dummy.next                   # the real head, even if it was removed

The second version has one loop, and the head is handled like any other node. The loop starts at the dummy, so cur.next is always a real node or None. The final return dummy.next is the step that matters most. If the head was removed, dummy.next is the new head. If you returned head instead, you would return a node that might have been removed from the list.

Trace the second version on 1 -> 1 -> 2 with target 1. cur starts at the dummy. cur.next is node 1, which matches, so the dummy's next jumps to the second 1. That node also matches, so the dummy's next jumps to 2. Node 2 does not match, so cur moves onto 2. The loop ends at None, and dummy.next is node 2. The list is 2.

The dummy node costs one extra node object, which is a small cost. The gain is that each function has one path instead of two, and fewer paths means fewer bugs.

Merging two sorted lists

Given two lists, each already sorted from smallest to largest, you can join them into one sorted list. The result has every value from both lists in order. The function does not create new nodes. It relinks the existing nodes, which is O(n + m) time for lists of lengths n and m, and O(1) extra space.

Think of two queues of people, each already ordered by height, merging into one line. At each step you look at the front person of each queue and move the shorter one into the new line. When one queue empties, the rest of the other queue joins the line unchanged, because it is already in order.

The algorithm has the same shape. Keep a tail that points at the last node of the merged list. While both input lists have nodes, take the smaller front node and append it to tail. Then attach whatever is left over from the list that still has nodes.

def merge(a, b):
    dummy = ListNode(0)
    tail = dummy
    while a is not None and b is not None:
        if a.val <= b.val:
            tail.next = a              # take a's front node
            a = a.next
        else:
            tail.next = b              # take b's front node
            b = b.next
        tail = tail.next               # the merged list grows by one
    tail.next = a if a is not None else b   # attach the leftover list
    return dummy.next

The dummy node gives the merged list a starting point before its first real node. Without it, the first append would need its own case to set the head. The <= test keeps equal values in the order they come, with the first list's value first. A sort is stable when equal values keep their original order, and <= is what keeps this merge stable.

The last line needs care. The expression a if a is not None else b means "use a when it is not None, otherwise use b". When one list runs out, the other list is already sorted and has no remaining neighbours to compare, so the function attaches it in one step.

Trace the function on 1 -> 3 -> 5 and 2 -> 4 -> 6. Each row shows the front nodes before a step and what the merged list holds afterward.

After step 5, list a is empty. The loop stops, and the tail attaches node 6 directly. No value is compared against a missing node, so no special case is needed for the end.

The next program merges two pairs of lists and prints the results. It takes no input, so it can run as it is.

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
1 -> 1 -> 3 -> 4 -> null

In the second call both lists start with 1. The function takes the first list's 1 because of <=, so the first list's value comes first. Then the 4 from the first list waits until the 3 from the second list is taken. When the second list is empty, the 4 is attached as the leftover.

Removing the nth node from the end

Suppose you want to delete the second node from the end of a list. The easy way is to count the nodes, then walk again to the node before the target. That takes two passes. The fixed-gap method does it in one pass.

Put two pointers at the dummy node. Move fast forward n steps first. Now fast and slow are n nodes apart. Then move both pointers together until fast is on the last node. At that moment the gap between them still holds, so slow is n nodes behind the last node, which means it is on the node just before the target. The target is slow.next, and removing it is a single link change.

Use the numbers from the example, a list 1 -> 2 -> 3 -> 4 -> 5 and n = 2. The second node from the end is 4, because 5 is the first from the end.

1. Start fast and slow at the dummy. Move fast 2 steps. It is now on node 2.
2. Move both while fast.next is not None. Pass 1: fast moves to 3 and slow moves to 1. Pass 2: fast moves to 4 and slow moves to 2. Pass 3: fast moves to 5 and slow moves to 3. Now fast.next is None, so the loop stops.
3. slow is on node 3, which is just before the target 4. Set slow.next = slow.next.next, which skips over node 4.

The result is 1 -> 2 -> 3 -> 5. The code is below.

def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head
    slow = dummy
    fast = dummy
    for _ in range(n):
        fast = fast.next                # move fast n steps ahead
    while fast.next is not None:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next          # skip the target
    return dummy.next

The dummy node is essential here. Removing the node n steps from the end is removing the head when n equals the length. In that case slow must stay on the dummy, and the dummy is the only node before the head. If both pointers started at the real head, fast would run off the end of the list, and there would be no node in front of the head to link from.

Trace the case where the head is removed. Take 1 -> 2 -> 3 with n = 3. fast moves 3 steps from the dummy and lands on node 3. The loop while fast.next is not None does not run, because node 3 has no next. slow is still on the dummy, and slow.next is node 1, the head. Setting slow.next = slow.next.next removes node 1, and the return value dummy.next is node 2. The head changed, and the function handled it without any special code.

Now the case with n equal to 1, where the last node is removed. For 1 -> 2 -> 3, fast moves 1 step to node 1. The loop moves slow to 1 and fast to 2, then slow to 2 and fast to 3, and stops when fast.next is None. Now slow is on 2, which is just before 3, and the link skips over node 3.

The function assumes that n is at most the length of the list. If n is larger, fast becomes None during the first loop, and the next line that reads fast.next fails. The module assignment prints no such song in that case, and the interview answer should mention the limit too.

The visualizer below uses two pointers with a gap, the same idea. Watch the gap stay constant while both pointers move, and watch the slow pointer stop just before the target.

The next program reads a list and a value of n from the input. If the list becomes empty, it prints empty list. Run it with this input. The first line is the number of values, the second line holds the values, and the third line is n:

5
1 2 3 4 5
2

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
 
 
def read_list():
    n = int(input())
    values = input().split()
    dummy = ListNode(0)
    tail = dummy
    for i in range(n):
        tail.next = ListNode(int(values[i]))
        tail = tail.next
    return dummy.next
 
 
def show(head):
    if head is None:
        print("empty list")
        return
    parts = []
    cur = head
    while cur is not None:
        parts.append(str(cur.val))
        cur = cur.next
    print(" -> ".join(parts + ["null"]))
 
 
def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head
    slow = dummy
    fast = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next is not None:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return dummy.next
 
 
head = read_list()
n = int(input())
show(remove_nth_from_end(head, n))

Output for the input above:

1 -> 2 -> 3 -> 5 -> null

Change the input to 1, then 1, then 1, which is a list of one node with n = 1, and the output is empty list. The function removes the only node, and dummy.next becomes None. The show function checks for that case, because printing null as a list would make the next reader wonder whether a crash happened.

Removing every node with a value

The dummy node pays off most when a function can remove any number of nodes, including the head and nodes next to each other. The function below removes every node holding a target value. It is the same loop as remove_with_dummy from earlier, placed in a complete program that reads its input.

Run it with this input. The list has three 1s spread along it, and the target is 1:

6
1 2 1 3 1 4
1

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
 
 
def read_list():
    n = int(input())
    values = input().split()
    dummy = ListNode(0)
    tail = dummy
    for i in range(n):
        tail.next = ListNode(int(values[i]))
        tail = tail.next
    return dummy.next
 
 
def show(head):
    if head is None:
        print("empty list")
        return
    parts = []
    cur = head
    while cur is not None:
        parts.append(str(cur.val))
        cur = cur.next
    print(" -> ".join(parts + ["null"]))
 
 
def remove_all(head, target):
    dummy = ListNode(0)
    dummy.next = head
    cur = dummy
    while cur.next is not None:
        if cur.next.val == target:
            cur.next = cur.next.next    # remove, and stay on cur
        else:
            cur = cur.next              # keep it, move on
    return dummy.next
 
 
head = read_list()
target = int(input())
show(remove_all(head, target))

Output for the input above:

2 -> 3 -> 4 -> null

The loop has two branches, and the important detail is the first one. After a removal, cur does not move, because the node that is now cur.next might also match. A value that appears three times in a row needs three removals, and the loop handles them because cur stays put until the next node does not match. If cur moved after every removal, it would skip a node and leave a match behind.

Finding where two lists meet

Two lists can share nodes. That happens when two lists are built from a common tail, as in a split of a larger structure, and it is a classic interview question. The question is not whether the values match. It is whether the two lists reach the same node object. The answer is the first shared node, or None if none exists.

The naive method checks every node of one list against every node of the other. That is O(n times m). The two-pointer method finds the answer in O(n + m) time with O(1) extra space. Each pointer walks its own list, and when a pointer reaches the end, it jumps to the head of the other list. Both pointers then cover the same total distance, so they meet at the shared node if there is one. If the lists do not meet, both become None at the same time and the loop ends.

Here is the reasoning in plain words. Say list A has x nodes before the shared part and list B has y nodes before it, and the shared part has z nodes. Pointer p walks A and then B. It covers x + z + y steps before it reaches the shared part. Pointer q walks B and then A, and it covers y + z + x steps. Both total the same number, so they arrive at the shared node together.

def get_intersection(a, b):
    p = a
    q = b
    while p is not q:
        p = b if p is None else p.next      # at the end, jump to the other head
        q = a if q is None else q.next
    return p                                # the shared node, or None if none

The comparison is p is not q, which checks whether the names point at the same node object. Two nodes with the same value are not the same node, and the question asks about the node. If the two lists do not share a node, the loop still ends, because both pointers become None at the same step, and None is None is true.

The program below builds two lists that share a tail of three nodes, then builds a third list that shares nothing. It prints the result for both.

Output:

intersection at value 8
no intersection

The shared node holds 8, and both lists lead to it. The lists have different lengths, five and four, and the two pointers still meet at the shared node because each one covers the same total distance. The list c holds 7 and shares no node with a, so the loop ends with both pointers at None.

Trace table: the switch-over

The switch-over is the part people find hardest, so here is the trace for the first pair of lists. List a is 1, 2, 8, 4, 5 and list b is 9, 8, 4, 5, where the 8 is the same object in both.

Pointer q ran off the end of b at step 4, and pointer p ran off the end of a at step 5. Then q jumped to the head of a at step 5, and p jumped to the head of b at step 6. The pointer that walked a now walks b, and the pointer that walked b now walks a. From step 6 on, they cover the same distance, and both reach the shared 8 at step 7.

Trace: removing the last node with n = 1

The case n = 1 is the one people get wrong most often, because the target is the last node and the pointers end in an unusual place. Use the list 1 -> 2 -> 3 -> 4 and n = 1, so the target is 4.

The last row is the one to check. slow stopped on node 3, which is the node just before the target. Setting slow.next = slow.next.next skips node 4, and the result is 1 -> 2 -> 3. Notice that the loop needed three passes, not four. It stops as soon as fast is on the last node, and that is the reason for the test fast.next is not None rather than fast is not None. If the second test were fast is not None, fast would step past the end into None, and slow would end on the target instead of before it.

Compare this with n = 4 on the same list, which removes the head. There fast ends on node 4 after the first loop, the second loop never runs, and slow stays on the dummy. The same code handles both cases, and the dummy is the reason.

Follow-up questions interviewers ask

Once you have written the basic functions, interviewers often push further. These are the answers that show you understand the trade-offs.

Can merge work without making new nodes? Yes, and the function in this lesson does exactly that: it relinks the existing nodes. The cost is that the original lists no longer exist as separate lists after the merge, because their nodes now belong to the merged result. If the caller needs the inputs afterward, copy each list first. A copy costs O(n + m) extra space, and you should say so. The standard library has heapq.merge, which merges sorted iterables, but it yields values and does not relink nodes, so the linked-list version still needs this merge.

How would you merge k sorted lists? Merge them in pairs, then merge the results in pairs again, until one list remains. Each round halves the count, so there are about log k rounds, and each round touches every node once. Another answer is a min-heap of the k front nodes, which you meet in module 21. Name both and say which one you would choose for a large k.

What if the lists are too large for memory? Then the lists are usually streams read from disk, and the merge reads one record from each stream at a time. The same comparison step applies, and only the two front records need to be in memory at once. This is the idea behind the merge phase of external sorting. You do not need the details for an entry-level interview, but knowing the idea shows that the algorithm does not depend on holding everything at once.

Is there a way to find the intersection without knowing the lengths? Yes. The switch-over method in this lesson needs no length, and it uses O(1) extra space. Counting the lengths first also works, and it can be simpler to explain. Mention both, then say which one you would write under time pressure.

Can you remove the nth node in a doubly linked list? Yes, and the walk can start from either end. Counting from the end is then a walk backward from the tail, which is the same as moving fast in the singly linked version. The removal itself is O(1) once you hold the node, as lesson 2 showed.

What happens inside: the cost of the tools

Each function in this lesson uses only a few variables, so the extra memory is constant, O(1). The dummy node is one object. The merge creates no new nodes, because it relinks the existing ones. The removal creates one dummy and links around the target. Compare that with a function that copies the values into a Python list, which needs O(n) space for the copy. The linked-list version is more careful about names and links, but it avoids the copy.

The time cost is the sum of the walks. Merge walks each list once, so O(n + m). The fixed-gap removal walks the list once, so O(n). The intersection walks at most each list twice, so O(n + m). These are the costs you should state in an interview, with a short reason for each.

Common mistakes and the messages you will see

Returning head instead of dummy.next. If the head was removed, head points at a node that is no longer in the list. The output looks like it contains a node that should be gone. Always return dummy.next when you used a dummy.

Forgetting the leftover attach in merge. If you write the loop but not the last line, the longer list loses its remaining nodes. The output is shorter than the input, and no error appears. Check the total count after a merge.

If the last line of merge is missing, merging 1 -> 3 with 2 -> 4 -> 6 prints 1 -> 2 -> 3 -> null. The 4 and the 6 are lost, and no error is raised.

Starting the fixed-gap pointers at the head. With both pointers on the real head, fast runs off the end when n equals the length, and removing the head has no node in front of it to link from. Start both at the dummy.

Calling remove_nth_from_end with n larger than the list. The first loop moves fast past the end, and then fast.next fails. The message is an AttributeError:

Calling remove_nth_from_end(build(1), 3) on a one-node list ends with these lines of the traceback:

    fast = fast.next
           ^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'next'

The line that reads fast.next ran while fast was None, because the one-node list has no third node to move onto. The fix is to check n <= length before the call, or to return None when fast becomes None in the first loop.

Comparing values in the intersection. Writing p.val != q.val finds equal values, not shared nodes. Two separate lists can hold the same numbers without sharing any node. Compare the names with is not. The two lists 1 -> 2 and 1 -> 2 built separately show the difference. The value version stops on the first 1 in each list and reports a match. The identity version returns None, because the lists share no node.

Modifying a list you still need. Merge and the intersection walk change the links. If you merge two lists and then print one of the original inputs, the printout shows the merged order, because the nodes now belong to the merged list. Copy a list first if you need both results.

Debugging walkthrough

Suppose the removal of the second node from the end of 1 -> 2 -> 3 -> 4 -> 5 prints 1 -> 2 -> 3 -> 4 -> null. The 5 was removed, not the 4. That tells you the gap is one too small: the pointer stopped on the node before the last node, not the one before the target.

Check the loop count. The first loop should move fast exactly n steps. Trace it with n = 2. After the first loop, fast is on node 2, which is two steps from the dummy. The second loop then moves slow and fast until fast.next is None. Count the passes on paper and write down slow and fast each time. You will find that slow is on node 3, so slow.next is node 4, and the code removes 4. If the output shows 5 removed instead, the bug is that fast moved only n - 1 steps. A one-line change fixes it, and the trace shows you where to make that change.

The routine is the same as in the earlier lessons: print the input, print the output, trace the pointers in a table and find the first row where the table disagrees with what you expected.

Variations and edge cases

Test each function on these inputs.

• A list of one node. Merge with an empty list returns the other list unchanged. Removing the 1st from the end of a one-node list empties it.
• Equal values in both lists. The <= choice keeps the first list's values first, and the output stays sorted.
• Lists of very different lengths. Merge attaches the long list's remaining nodes. The intersection still meets at the shared node.
• Two empty lists. Merge returns None. The intersection returns None at once, because p and q are both None from the start.
• Removing the head with the fixed gap. Use n equal to the length.

Why merge needs sorted input

The merge function is correct only when both inputs are sorted. The rule it uses is "take the smaller of the two front values". That rule gives a sorted result only if each list is already sorted, because the front of a list is then its smallest value. If a list is unsorted, a small value can sit deep inside it, and the merge takes the larger front first, which breaks the order.

A simple test shows the problem. Merge 3 -> 1 with 2. The fronts are 3 and 2, so the function takes 2 first. Then the fronts are 3 and None, so it takes 3, and the output is 2 -> 3 -> 1. The output is not sorted, and the function did nothing wrong by its own rule. The bug is in the input. When you cannot trust the input, sort each list first, which costs O(n log n), or check each list before merging.

Interview patterns

The dummy node. Use it whenever the head can change. Say this out loud, and return dummy.next.

Merge two sorted inputs. Compare the fronts, relink the smaller, and attach the leftover. Mention that the operation is O(n + m) and that merge sort uses it.

The fixed gap. Move one pointer n steps ahead, then move both together until the ahead pointer is on the last node. Explain that the slow pointer is then on the node before the target.

The switch-over. When two lists must be compared from their ends, walk each list and then the other. Explain that both pointers cover the same total distance.

Real-world uses

Merging sorted sequences is everywhere. Systems that combine log files written in time order merge several sorted streams of records into one. Removing the nth item from the end is useful whenever the length is unknown in advance, such as a stream of messages where you want to drop the one that is third from the newest. Finding a shared node is how some systems detect that two references lead to the same record. The dummy node is a general tool.

Practice

Try these before you open the answers. Trace each function on a short list before you write the code.

Exercise 1 (easy). Merge 1 -> 4 and 1 -> 3 by hand, with a trace table. Write down each step.

Show the answer

The result is 1 -> 1 -> 3 -> 4. The first list's 1 comes first because of the <= test.

Exercise 2 (easy). Explain in plain words why the dummy node makes remove_nth_from_end correct when n equals the list length.

Show the answer

When n equals the length, fast moves to the last node and the second loop does not run. slow is still on the dummy, which is the node before the head. The target is slow.next, which is the real head. Removing it needs a node before it, and the dummy provides that node. Without the dummy, the code would need a special case for removing the head.

Exercise 3 (easy). Write has_intersection(a, b) that returns True when the two lists share a node.

Show the answer

The function reuses get_intersection from this lesson. It returns True exactly when that function finds a shared node, because get_intersection returns None only when no shared node exists.

def has_intersection(a, b):
    return get_intersection(a, b) is not None

Exercise 4 (medium). Write remove_all_no_dummy(head, target) without a dummy node. Your code must handle the head as a separate case.

Show the answer

The first loop is the special case the dummy removes. After it, the head holds a value that is not the target, and the second loop works as in the lesson. Count the lines: this version is longer and has two paths.

def remove_all_no_dummy(head, target):
    while head is not None and head.val == target:
        head = head.next                # clear the matching nodes at the front
    if head is None:
        return None
    cur = head
    while cur.next is not None:
        if cur.next.val == target:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return head

Exercise 5 (medium). Write a recursive merge, merge_rec(a, b). The result must be the same as merge.

Show the answer

Each call picks the smaller front node, links it to the merged result of the rest, and returns it. The base cases handle an empty list. The recursion depth is at most n + m, so this uses O(n + m) call-stack space, while the iterative merge uses O(1). For a long list, the iterative version is the safer choice, for the same reason as in lesson 3.

def merge_rec(a, b):
    if a is None:
        return b
    if b is None:
        return a
    if a.val <= b.val:
        a.next = merge_rec(a.next, b)   # a stays first, the rest is merged after it
        return a
    else:
        b.next = merge_rec(a, b.next)
        return b

Exercise 6 (medium). Write remove_first_k(head, k) that removes the first k nodes and returns the new head. If the list is shorter than k, return None.

Show the answer

Walking past k nodes gives the first node that stays. If the list runs out first, cur is None, which is the correct answer for a list shorter than k. The original nodes are not changed.

def remove_first_k(head, k):
    cur = head
    i = 0
    while i < k and cur is not None:
        cur = cur.next                  # walk past the first k nodes
        i += 1
    return cur                          # None when the list is shorter than k

Exercise 7 (hard). Merge k sorted lists by merging them in pairs, repeating until one list remains. Write merge_all(lists), where lists is a Python list of head nodes.

Show the answer

Each round halves the number of lists, so there are about log k rounds. A round merges every pair, and each node is visited once per round, so the total time is O(N log k) for N nodes in all. The merge function is the one from this lesson.

def merge_all(lists):
    if len(lists) == 0:
        return None
    current = list(lists)
    while len(current) > 1:
        nxt = []
        for i in range(0, len(current), 2):
            a = current[i]
            b = current[i + 1] if i + 1 < len(current) else None
            nxt.append(merge(a, b))
        current = nxt
    return current[0]

Exercise 8 (hard). Sort a linked list with merge sort. Write sort_list(head).

Show the answer

The middle is found with the slow and fast pointers from lesson 3. The slow.next = None line cuts the list, which is the step people forget. Without it, the first half still holds the whole second half, so the recursion keeps calling itself on the same list. The merge of two sorted halves is the function from this lesson, so the whole sort is O(n log n) time.

def sort_list(head):
    if head is None or head.next is None:
        return head
    slow = head
    fast = head.next
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None                    # cut the list into two halves
    return merge(sort_list(head), sort_list(second))

Exercise 9 (medium). Two numbers are stored as linked lists of digits, least significant digit first. For example, 2 -> 4 -> 3 is 342. Write add_two(a, b) that returns the digits of the sum in the same form.

Show the answer

The lists are stored least significant digit first, so the digits are added from the front, exactly as a person adds on paper. The carry holds a 1 when a sum is 10 or more. The loop continues while either list has digits or a carry is left, which handles a final carry such as 5 + 5 = 10. The dummy node collects the result without a special case for its first digit.

def add_two(a, b):
    dummy = ListNode(0)
    tail = dummy
    carry = 0
    while a is not None or b is not None or carry != 0:
        total = carry
        if a is not None:
            total += a.val
            a = a.next
        if b is not None:
            total += b.val
            b = b.next
        tail.next = ListNode(total % 10)
        tail = tail.next
        carry = total // 10
    return dummy.next

Exercise 10 (medium). Partition a list around a value x. All nodes with values less than x come first, then all nodes with values at least x. Keep the original order inside each group. Write partition(head, x).

Show the answer

Two dummy nodes build two lists, one of small values and one of the rest, and each keeps the order of the original. The final high.next = None matters, because the last node of the original list may still point at a node that moved to the low list. Cutting that link prevents a cycle.

def partition(head, x):
    low_dummy = ListNode(0)
    high_dummy = ListNode(0)
    low = low_dummy
    high = high_dummy
    cur = head
    while cur is not None:
        if cur.val < x:
            low.next = cur
            low = cur
        else:
            high.next = cur
            high = cur
        cur = cur.next
    high.next = None
    low.next = high_dummy.next
    return low_dummy.next

What you now know

• A dummy node is a placeholder before the real head. It removes the special case for the first node, and you return dummy.next.
• Merging two sorted lists relinks the smaller front node each time, then attaches the leftover list in one step.
• Removing the nth node from the end uses a fixed gap: move fast n steps ahead, then move both pointers until fast is on the last node.
• Removing every node with a value needs the dummy node, and cur must not move after a removal.
• Two lists that share a tail can be compared with two pointers that switch heads, which meet at the first shared node.
• Each of these functions uses O(1) extra space, and each costs one or two walks over the input.