Linked List Algorithms: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Linked List Algorithms: Complete Guide with Examples

If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the pointer-manipulation code you can memorize and adapt during an interview. Every template here runs in

O(N)

time with

O(1)

extra space unless otherwise noted.

Main Template: Reverse a Linked List

This is the most common linked list operation and the building block for palindrome checks, reordering, and group reversal. Three pointers walk the list: prev tracks the reversed prefix, current is the node being processed, and next keeps the rest of the list reachable.

Use this for Reverse Linked List .

function reverseList(head) {
    let prev = null;
    let current = head;

    while (current !== null) {
        // Save the node after current before its pointer is
        // overwritten, or the rest of the list is unreachable.
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    current = head

    while current is not None:
        # Capture the successor first. current.next is about
        # to be overwritten, and the rest of the list lives
        # behind that pointer.
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;

    while (current != nullptr) {
        ListNode* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    current := head

    for current != nil {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }

    return prev
}

def reverse_list(head)
    prev = nil
    current = head

    while current
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    end

    prev
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

prev: the last processed node. It starts as null because the first node points to nothing once the list is reversed.
current: the node being processed. It starts at the head and walks forward.
next: the saved successor of current, captured before current.next is overwritten.

Visual Mechanism

    stateDiagram-v2
    [*] --> Init: prev = null, current = head
    Init --> Check: current != null
    Check --> Save: next = current.next
    Save --> Rewire: current.next = prev
    Rewire --> Advance: prev = current, current = next
    Advance --> Check
    Check --> Done: current == null
    Done --> [*]: return prev

Critical Sections

The initialization sets prev to null because the first node becomes the last node of the reversed list. Its pointer must point to nothing.

The save step is the part people skip under pressure. current.next is about to be overwritten, and next is the only reference to the rest of the list. Without it, the loop terminates after one iteration.

The advance step moves the whole window forward. prev takes the position of current, and current takes the saved next. Both assignments must happen before the next iteration, and the order between them does not matter.

Variations

1. Find the Middle Node (Fast and Slow)

When you need the middle of a list, or a split point for palindrome and reorder problems, one pointer moving twice as fast as the other lands at the middle by the time it reaches the end.

Use this for Middle of the Linked List and Palindrome Linked List .

function findMiddle(head) {
    let slow = head;
    let fast = head;

    // fast covers two nodes per step, so it reaches the end
    // exactly when slow has covered half the list.
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

def find_middle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = head
    fast = head

    # The fast pointer advances two nodes per step. Its second
    # step needs fast.next to exist, so both are checked.
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    return slow

public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

ListNode* findMiddle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

Visual

    graph LR
    A["slow = fast = head"] --> B{"fast and fast.next exist?"}
    B -->|Yes| C["slow +1, fast +2"]
    C --> B
    B -->|No| D["return slow"]

2. Remove the k-th Node From the End (Dummy Node)

When a problem asks for the k-th node from the end, two pointers separated by k steps find it in one pass without knowing the list length. The dummy head protects the case where the node to remove is the head itself.

Use this for Remove Nth Node From End of List .

function removeNthFromEnd(head, n) {
    // The dummy node makes head removal identical to any other
    // removal, so the delete code has no special case.
    const dummy = new ListNode(0, head);
    let first = dummy;
    let second = dummy;

    // first starts n+1 nodes ahead, so when it reaches the end,
    // second is the predecessor of the target node.
    for (let i = 0; i <= n; i++) {
        first = first.next;
    }

    while (first !== null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next;
    return dummy.next;
}

def remove_nth_from_end(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    first = dummy
    second = dummy

    for _ in range(n + 1):
        first = first.next

    while first is not None:
        first = first.next
        second = second.next

    second.next = second.next.next
    return dummy.next

def remove_nth_from_end(head, n)
    dummy = ListNode.new(0, head)
    first = dummy
    second = dummy

    (n + 1).times do
        first = first.next
    end

    while first
        first = first.next
        second = second.next
    end

    second.next = second.next.next
    dummy.next
end

Visual

    graph LR
    A["dummy -> head"] --> B["first advances n+1 steps"]
    B --> C["first and second walk together"]
    C --> D["first reaches null"]
    D --> E["second sits before the target node"]
    E --> F["skip the target node"]

3. Merge Two Sorted Lists (Dummy Node)

Merging two sorted lists builds a new list with a tail pointer. The dummy node means the first append needs no special case, and the same loop handles both lists.

The practice problem Merge Two Sorted Lists is covered on the divide and conquer problems page .

function mergeTwoLists(list1, list2) {
    // dummy.next is the result head, so appending the first
    // node needs no special case.
    const dummy = new ListNode(0);
    let tail = dummy;

    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }

    // One list is exhausted. The other is already sorted,
    // so append what is left of it whole.
    tail.next = list1 !== null ? list1 : list2;
    return dummy.next;
}

def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    tail = dummy

    while list1 is not None and list2 is not None:
        if list1.val < list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next

    # One input is empty, so the remainder of the other input
    # is already sorted and can be attached as a whole chain.
    tail.next = list1 if list1 is not None else list2
    return dummy.next

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }

    tail.next = list1 != null ? list1 : list2;
    return dummy.next;
}

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;

    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    tail->next = list1 != nullptr ? list1 : list2;
    return dummy->next;
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }

    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }
    return dummy.Next
}

def merge_two_lists(list1, list2)
    dummy = ListNode.new(0)
    tail = dummy

    while list1 && list2
        if list1.val < list2.val
            tail.next = list1
            list1 = list1.next
        else
            tail.next = list2
            list2 = list2.next
        end
        tail = tail.next
    end

    tail.next = list1 || list2
    dummy.next
end

Visual

    graph LR
    A["dummy and tail"] --> B{"both lists non-empty?"}
    B -->|Yes| C["append the smaller head, advance that list"]
    C --> B
    B -->|No| D["append the rest of the remaining list"]
    D --> E["return dummy.next"]

4. Detect a Cycle (Floyd’s Algorithm)

A cycle makes a naive traversal run forever. Two pointers at different speeds meet inside a cycle, and they can only meet if a cycle exists.

The practice problems Linked List Cycle and Linked List Cycle II are covered on the cycle detection problems page .

function hasCycle(head) {
    let slow = head;
    let fast = head;

    // The second step of fast dereferences fast.next, so the
    // loop must confirm it exists on every iteration.
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;

        // In a cycle, fast gains one node per step on slow
        // and eventually laps it. Meeting proves a cycle.
        if (slow === fast) return true;
    }

    return false;
}

def has_cycle(head: Optional[ListNode]) -> bool:
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) return true;
    }

    return false;
}

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) return true;
    }

    return false;
}

Visual

    graph LR
    A["slow = fast = head"] --> B{"fast and fast.next exist?"}
    B -->|Yes| C["slow +1, fast +2"]
    C --> D{"slow == fast?"}
    D -->|Yes| E["cycle found"]
    D -->|No| B
    B -->|No| F["no cycle"]

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .