Coding Patterns
Linked List
Code Templates

Code Templates

Master linked list manipulation with these standardized code templates. Each template provides implementations in JavaScript, Python, Java, C++, Go, and Ruby with detailed explanations of pointer techniques. Refer back to the Concept Guide for the theoretical foundation.

Main Template: Reverse a Linked List

This is the fundamental template for reversing a linked list, which is used in many problems including palindrome checking and list reordering. This template directly applies to the Reverse Linked List problem.

Template Implementation 

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

    while (current !== null) {
        const next = current.next;  // Save next node
        current.next = prev;         // Reverse pointer
        prev = current;              // Move prev forward
        current = next;              // Move current forward
    }

    return prev; // New head
}
def reverse_list(head):
    prev = None
    current = head

    while current is not None:
        next_node = current.next  # Save next node
        current.next = prev       # Reverse pointer
        prev = current            # Move prev forward
        current = next_node       # Move current forward

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

    while (current != null) {
        ListNode next = current.next;  // Save next node
        current.next = prev;         // Reverse pointer
        prev = current;              // Move prev forward
        current = next;              // Move current forward
    }

    return prev; // New head
}
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;

    while (current != nullptr) {
        ListNode* next = current->next;  // Save next node
        current->next = prev;           // Reverse pointer
        prev = current;                // Move prev forward
        current = next;                // Move current forward
    }

    return prev; // New head
}
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    current := head

    for current != nil {
        next := current.Next  // Save next node
        current.Next = prev  // Reverse pointer
        prev = current      // Move prev forward
        current = next      // Move current forward
    }

    return prev // New head
}
def reverse_list(head)
  prev = nil
  current = head

  while current
    next_node = current.next  # Save next node
    current.next = prev       # Reverse pointer
    prev = current            # Move prev forward
    current = next_node       # Move current forward
  end

  prev # New head
end

Code Breakdown

Key Variables:

  • prev: Tracks the previously processed node. Initially null because the first node will point to nothing when reversed.
  • current: The node currently being processed. Starts at the head and moves forward.
  • next: A temporary variable to save the next node before we overwrite current.next.

Algorithm Visualization:

  stateDiagram-v2
    [*] --> Start
    Start --> Check: current != null
    Check --> Save: Save current.next
    Save --> Reverse: current.next = prev
    Reverse --> MovePrev: prev = current
    MovePrev --> MoveCurrent: current = next
    MoveCurrent --> Check
    Check --> End: current == null
    End --> [*]: return prev

    note right of Save
        Must save before
        overwriting!
    end note

    note right of Reverse
        This is the core
        pointer reversal
    end note

Critical Sections:

  1. Initialization: prev = null, current = head. The first node after reversal will be the last node, so its next should point to null.

  2. Saving Next: Before modifying current.next, we MUST save it to next. If we don’t, we lose the reference to the rest of the list.

  3. Reversing Pointer: current.next = prev changes the pointer direction from forward to backward.

  4. Moving Pointers: Move both pointers forward. prev takes the place of current, and current takes the place of the saved next.

Variations

Two Pointer: Find Middle Node

Useful for problems like Palindrome Linked List.

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

    while (fast !== null && fast.next !== null) {
        slow = slow.next;      // Move 1 step
        fast = fast.next.next; // Move 2 steps
    }

    return slow; // Middle node
}
def find_middle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next      # Move 1 step
        fast = fast.next.next # Move 2 steps

    return slow # Middle node
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; // Middle node
}
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; // Middle node
}
func findMiddle(head *ListNode) *ListNode {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next      // Move 1 step
        fast = fast.Next.Next // Move 2 steps
    }

    return slow // Middle node
}
def find_middle(head)
  slow = fast = head

  while fast && fast.next
    slow = slow.next      # Move 1 step
    fast = fast.next.next # Move 2 steps
  end

  slow # Middle node
end

Cycle Detection: Floyd’s Algorithm

Detect if a cycle exists in a linked list. Directly applies to Linked List Cycle.

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

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

        if (slow === fast) return true;
    }

    return false;
}
def has_cycle(head):
    slow = fast = head

    while fast and fast.next:
        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;
}
func hasCycle(head *ListNode) bool {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            return true
        }
    }

    return false
}
def has_cycle(head)
  slow = fast = head

  while fast && fast.next
    slow = slow.next
    fast = fast.next.next

    return true if slow == fast
  end

  false
end

Merge Two Sorted Lists

Merge two sorted lists into one sorted list. Directly applies to Merge Two Sorted Lists.

function mergeTwoLists(list1, list2) {
    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;
    }

    // Append remaining nodes
    tail.next = list1 !== null ? list1 : list2;

    return dummy.next;
}
def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    tail = dummy

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

    # Append remaining nodes
    tail.next = list1 or 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;
    }

    // Append remaining nodes
    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;
    }

    // Append remaining nodes
    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
    }

    // Append remaining nodes
    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

  # Append remaining nodes
  tail.next = list1 || list2

  dummy.next
end

Practice

Ready to apply these templates? Visit our Practice Problems to solve real interview questions using these patterns.

Pro Tip: The dummy node pattern is essential for safe head manipulation in linked list problems. Always create a dummy node pointing to the head when you need to modify the beginning of the list or need a consistent starting point for pointer operations.