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.
Merge, Split, and Find Nth from End is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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]))))Tracing the Merge Step by Step
Trace mergeTwoLists([1,2,4], [1,3,4]): compare 1 and 1 — pick l1(1), advance l1 to 2. Compare 2 and 1 — pick l2(1), advance l2 to 3. Compare 2 and 3 — pick l1(2), advance l1 to 4. Compare 4 and 3 — pick l2(3), advance l2 to 4. Compare 4 and 4 — pick l1(4), advance l1 to None. Attach remaining l2(4). Result: [1,1,2,3,4,4].
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
step = 0
while l1 and l2:
step += 1
if l1.val <= l2.val:
print(f'Step {step}: pick l1({l1.val})')
curr.next = l1; l1 = l1.next
else:
print(f'Step {step}: pick l2({l2.val})')
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
mergeTwoLists(build([1,2,4]),build([1,3,4]))Finding the Midpoint with Slow-Fast
To split a list at its midpoint, use the slow-fast pointer pattern. slow advances 1 step; fast advances 2 steps. When fast reaches None (or the last node), slow is at the midpoint. For an even-length list this gives the first of the two middle nodes, which is conventional for merge-sort splitting.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_at_mid(head):
'''Returns (first_half_head, second_half_head).'''
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # second half starts here
slow.next = None # sever the list
return head, mid
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
head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second)) # [1,2,3] [4,5]Merge Sort on a Linked List
LeetCode 148 'Sort List': sort a linked list in O(n log n) time, O(log n) space. The approach: split the list at the midpoint, recursively sort each half, and merge. Linked-list merge sort is natural because splitting at the midpoint is O(n) (not O(1) like arrays), but the overall complexity is still O(n log n) with only O(log n) stack space.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head):
if not head or not head.next:
return head
# Split
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# Recurse
left = sortList(head)
right = sortList(mid)
# Merge
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val <= right.val:
curr.next = left; left = left.next
else:
curr.next = right; right = right.next
curr = curr.next
curr.next = left or right
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(sortList(build([4,2,1,3])))) # [1,2,3,4]Finding the Nth Node from End
LeetCode 19 'Remove Nth Node From End of List': find the nth node from the tail in a single pass. Use two pointers separated by exactly n nodes. Advance fast n steps ahead of slow. Then advance both together until fast reaches the last node. At that point slow is at the (n+1)th node from the end — the predecessor of the node to remove.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1): # advance fast n+1 steps
fast = fast.next
slow = dummy
while fast: # advance both until fast is None
slow = slow.next
fast = fast.next
slow.next = slow.next.next # remove nth node
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(removeNthFromEnd(build([1,2,3,4,5]), 2))) # [1,2,3,5]Why n+1 Steps in Remove Nth
The key subtlety is advancing fast by n+1 steps (not n) from the dummy head. After n+1 steps, fast is n+1 ahead of slow (both starting at dummy). When fast reaches None (one past the tail), slow is n+1 positions before None — meaning slow is at position (length - n - 1) from zero, or the predecessor of the target. This allows slow.next = slow.next.next to delete the nth-from-last node cleanly.
# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow) 1 2 3(fast) 4 5 None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')Intersection of Two Linked Lists
LeetCode 160 'Intersection of Two Linked Lists': find the node where two lists first intersect. The O(1) space trick: advance two pointers, one per list. When a pointer reaches None, redirect it to the head of the other list. After at most len(A) + len(B) steps both pointers have traveled the same total distance and must be at the intersection node (or both at None if no intersection).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a # None if no intersection
# Build: A: 4->1->\ B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val) # 8Merge K Sorted Lists (Divide and Conquer)
LeetCode 23 'Merge K Sorted Lists': given k sorted lists, merge them into one. The optimal approach: repeatedly merge pairs of lists using divide and conquer, halving the number of lists each round. With k lists of average length n, this takes O(n k log k) time versus O(n k²) for sequential merging. A min-heap approach is also O(n k log k).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
def merge_two(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
return dummy.next
if not lists: return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i+1 < len(lists) else None
merged.append(merge_two(l1, l2))
lists = merged
return lists[0]
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
lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists))) # [1,1,2,3,4,4,5,6]Odd-Even Linked List
LeetCode 328 'Odd Even Linked List': group all odd-indexed nodes first, then even-indexed nodes (1-indexed). The approach: maintain two separate chains (odd and even), connect them when done. One pass through the list suffices, giving O(n) time and O(1) space. This is a clean example of simultaneously advancing two pointers with different strides.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
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(oddEvenList(build([1,2,3,4,5])))) # [1,3,5,2,4]Putting It All Together
The three patterns in this lesson — merge sorted lists, split at midpoint, find nth from end — share a common theme: use extra pointer variables to track positions without additional memory. The dummy head simplifies merge and deletion; the slow-fast gap pins a specific relative position; advancing one pointer first creates the desired separation.
In an interview, name the pattern you are using before coding: 'I will use the two-pointer gap technique to find the nth from end in one pass.' This demonstrates structured thinking.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: merging two sorted lists uses a dummy head and at-each-step comparison for O(n+m) O(1) space, splitting at the midpoint uses slow-fast pointers with fast stopping at the last valid pair, and finding the nth from end advances fast n+1 steps ahead so slow lands at the predecessor. Next up we build stacks and queues and apply them to classic interview problems.
Frequently asked questions
Is the “Merge, Split, and Find Nth from End” lesson free?
Yes — the full text of “Merge, Split, and Find Nth from End” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Merge, Split, and Find Nth from End” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Node Class and List Construction
- Reversing a Linked List
- Cycle Detection with Floyd's Algorithm
- Merge, Split, and Find Nth from End