Linked List Operations

Dec 13, 2025 · 10 min read · linked-list data-structures two-pointers algorithms ·

Share on:

Optimal techniques for common linked list operations using pointer manipulation, particularly the two-pointer (slow/fast) and three-pointer techniques.

Linked List Structure

 1type ListNode struct {
 2    Val  int
 3    Next *ListNode
 4}
 5
 6// Helper to create a list from array
 7func CreateList(values []int) *ListNode {
 8    if len(values) == 0 {
 9        return nil
10    }
11    
12    head := &ListNode{Val: values[0]}
13    current := head
14    
15    for i := 1; i < len(values); i++ {
16        current.Next = &ListNode{Val: values[i]}
17        current = current.Next
18    }
19    
20    return head
21}
22
23// Helper to print list
24func PrintList(head *ListNode) {
25    for head != nil {
26        fmt.Printf("%d -> ", head.Val)
27        head = head.Next
28    }
29    fmt.Println("nil")
30}

Two-Pointer Technique (Slow/Fast)

Use two pointers moving at different speeds.

Pattern:

Slow pointer: Moves 1 step at a time
Fast pointer: Moves 2 steps at a time

1. Find Middle of List

For odd length: Return middle node
For even length: Return second middle node

Visualization

Slow moves: 1 → 2 → 3
Fast moves: 1 → 3 → 5 → nil

Go Implementation

 1func FindMiddle(head *ListNode) *ListNode {
 2    if head == nil {
 3        return nil
 4    }
 5    
 6    slow, fast := head, head
 7    
 8    // When fast reaches end, slow is at middle
 9    for fast != nil && fast.Next != nil {
10        slow = slow.Next      // Move 1 step
11        fast = fast.Next.Next // Move 2 steps
12    }
13    
14    return slow
15}
16
17// Example
18func main() {
19    list := CreateList([]int{1, 2, 3, 4, 5})
20    middle := FindMiddle(list)
21    fmt.Println("Middle:", middle.Val) // 3
22}

Time: $O(n)$, Space: $O(1)$

2. Detect Cycle

Detect if list has a cycle using Floyd's algorithm.

Visualization

Go Implementation

 1func HasCycle(head *ListNode) bool {
 2    if head == nil {
 3        return false
 4    }
 5    
 6    slow, fast := head, head
 7    
 8    for fast != nil && fast.Next != nil {
 9        slow = slow.Next
10        fast = fast.Next.Next
11        
12        if slow == fast {
13            return true // Cycle detected
14        }
15    }
16    
17    return false
18}

Time: $O(n)$, Space: $O(1)$

3. Find Cycle Start

Find the node where cycle begins.

Algorithm

Detect cycle using slow/fast pointers
Move slow to head
Move both pointers 1 step at a time
They meet at cycle start

Go Implementation

 1func DetectCycle(head *ListNode) *ListNode {
 2    if head == nil {
 3        return nil
 4    }
 5    
 6    // Phase 1: Detect cycle
 7    slow, fast := head, head
 8    hasCycle := false
 9    
10    for fast != nil && fast.Next != nil {
11        slow = slow.Next
12        fast = fast.Next.Next
13        
14        if slow == fast {
15            hasCycle = true
16            break
17        }
18    }
19    
20    if !hasCycle {
21        return nil
22    }
23    
24    // Phase 2: Find cycle start
25    slow = head
26    for slow != fast {
27        slow = slow.Next
28        fast = fast.Next
29    }
30    
31    return slow
32}

Time: $O(n)$, Space: $O(1)$

4. Reverse Linked List

Visualization

Go Implementation

 1func ReverseList(head *ListNode) *ListNode {
 2    var prev *ListNode
 3    curr := head
 4    
 5    for curr != nil {
 6        next := curr.Next  // Save next
 7        curr.Next = prev   // Reverse pointer
 8        prev = curr        // Move prev forward
 9        curr = next        // Move curr forward
10    }
11    
12    return prev // New head
13}
14
15// Example
16func main() {
17    list := CreateList([]int{1, 2, 3, 4, 5})
18    PrintList(list)           // 1 -> 2 -> 3 -> 4 -> 5 -> nil
19    reversed := ReverseList(list)
20    PrintList(reversed)       // 5 -> 4 -> 3 -> 2 -> 1 -> nil
21}

Time: $O(n)$, Space: $O(1)$

5. Check Palindrome

Visualization

Algorithm

Find middle using slow/fast pointers
Reverse second half
Compare first half with reversed second half

Go Implementation

 1func IsPalindrome(head *ListNode) bool {
 2    if head == nil || head.Next == nil {
 3        return true
 4    }
 5    
 6    // Find middle
 7    slow, fast := head, head
 8    for fast != nil && fast.Next != nil {
 9        slow = slow.Next
10        fast = fast.Next.Next
11    }
12    
13    // Reverse second half
14    secondHalf := ReverseList(slow)
15    
16    // Compare
17    firstHalf := head
18    for secondHalf != nil {
19        if firstHalf.Val != secondHalf.Val {
20            return false
21        }
22        firstHalf = firstHalf.Next
23        secondHalf = secondHalf.Next
24    }
25    
26    return true
27}

Time: $O(n)$, Space: $O(1)$

6. Remove N-th Node From End

Visualization

Remove 2nd from end (node 4)

Algorithm

Use two pointers with N gap between them.

Go Implementation

 1func RemoveNthFromEnd(head *ListNode, n int) *ListNode {
 2    dummy := &ListNode{Next: head}
 3    first, second := dummy, dummy
 4    
 5    // Move first n+1 steps ahead
 6    for i := 0; i <= n; i++ {
 7        first = first.Next
 8    }
 9    
10    // Move both until first reaches end
11    for first != nil {
12        first = first.Next
13        second = second.Next
14    }
15    
16    // Remove node
17    second.Next = second.Next.Next
18    
19    return dummy.Next
20}

Time: $O(n)$, Space: $O(1)$

7. Find Intersection of Two Lists

Visualization

Go Implementation

 1func GetIntersectionNode(headA, headB *ListNode) *ListNode {
 2    if headA == nil || headB == nil {
 3        return nil
 4    }
 5    
 6    pA, pB := headA, headB
 7    
 8    // Traverse both lists
 9    // When reaching end, jump to other list's head
10    for pA != pB {
11        if pA == nil {
12            pA = headB
13        } else {
14            pA = pA.Next
15        }
16        
17        if pB == nil {
18            pB = headA
19        } else {
20            pB = pB.Next
21        }
22    }
23    
24    return pA // Either intersection or nil
25}

Time: $O(m + n)$, Space: $O(1)$

Why this works: Both pointers travel same distance: $m + n - k$ where $k$ is common length.

8. Merge Two Sorted Lists

Visualization

Go Implementation

 1func MergeTwoLists(l1, l2 *ListNode) *ListNode {
 2    dummy := &ListNode{}
 3    curr := dummy
 4    
 5    for l1 != nil && l2 != nil {
 6        if l1.Val <= l2.Val {
 7            curr.Next = l1
 8            l1 = l1.Next
 9        } else {
10            curr.Next = l2
11            l2 = l2.Next
12        }
13        curr = curr.Next
14    }
15    
16    // Attach remaining nodes
17    if l1 != nil {
18        curr.Next = l1
19    } else {
20        curr.Next = l2
21    }
22    
23    return dummy.Next
24}

Time: $O(m + n)$, Space: $O(1)$

9. Compare Two Lists (Equality)

Check if two lists are identical.

 1func AreListsEqual(l1, l2 *ListNode) bool {
 2    for l1 != nil && l2 != nil {
 3        if l1.Val != l2.Val {
 4            return false
 5        }
 6        l1 = l1.Next
 7        l2 = l2.Next
 8    }
 9    
10    // Both should be nil
11    return l1 == nil && l2 == nil
12}

Time: $O(min(m, n))$, Space: $O(1)$

10. Find Difference of Two Lists (A - B)

Find nodes in list A that are not in list B, with $O(1)$ space.

Algorithm

For each node in A, traverse B to check if it exists. Not efficient but $O(1)$ space.

 1// Returns values in A that are not in B
 2func ListDifference(a, b *ListNode) []int {
 3    result := []int{}
 4    
 5    for currA := a; currA != nil; currA = currA.Next {
 6        found := false
 7        
 8        // Check if currA.Val exists in B
 9        for currB := b; currB != nil; currB = currB.Next {
10            if currA.Val == currB.Val {
11                found = true
12                break
13            }
14        }
15        
16        if !found {
17            result = append(result, currA.Val)
18        }
19    }
20    
21    return result
22}

Time: $O(m \times n)$, Space: $O(1)$ (excluding result)

Better Approach: Sort First

If we can modify the lists, sort them first:

 1func ListDifferenceSorted(a, b *ListNode) []int {
 2    // Assume lists are sorted or sort them first
 3    result := []int{}
 4    
 5    for a != nil && b != nil {
 6        if a.Val < b.Val {
 7            result = append(result, a.Val)
 8            a = a.Next
 9        } else if a.Val > b.Val {
10            b = b.Next
11        } else {
12            // Equal, skip both
13            a = a.Next
14            b = b.Next
15        }
16    }
17    
18    // Add remaining from A
19    for a != nil {
20        result = append(result, a.Val)
21        a = a.Next
22    }
23    
24    return result
25}

Time: $O(m + n)$ if already sorted, Space: $O(1)$

11. Find Intersection (Common Elements) with O(1) Space

Find values that appear in both lists.

 1// Returns values that appear in both A and B
 2func ListIntersection(a, b *ListNode) []int {
 3    result := []int{}
 4    
 5    for currA := a; currA != nil; currA = currA.Next {
 6        // Check if currA.Val exists in B
 7        for currB := b; currB != nil; currB = currB.Next {
 8            if currA.Val == currB.Val {
 9                // Check if not already in result
10                alreadyAdded := false
11                for _, v := range result {
12                    if v == currA.Val {
13                        alreadyAdded = true
14                        break
15                    }
16                }
17                if !alreadyAdded {
18                    result = append(result, currA.Val)
19                }
20                break
21            }
22        }
23    }
24    
25    return result
26}
27
28// Better: If lists are sorted
29func ListIntersectionSorted(a, b *ListNode) []int {
30    result := []int{}
31    
32    for a != nil && b != nil {
33        if a.Val < b.Val {
34            a = a.Next
35        } else if a.Val > b.Val {
36            b = b.Next
37        } else {
38            // Equal - add to result
39            if len(result) == 0 || result[len(result)-1] != a.Val {
40                result = append(result, a.Val)
41            }
42            a = a.Next
43            b = b.Next
44        }
45    }
46    
47    return result
48}

Time: $O(m \times n)$ unsorted, $O(m + n)$ sorted
Space: $O(1)$ (excluding result)

12. Reorder List (L0 → Ln → L1 → Ln-1 → ...)

Visualization

Go Implementation

 1func ReorderList(head *ListNode) {
 2    if head == nil || head.Next == nil {
 3        return
 4    }
 5    
 6    // Find middle
 7    slow, fast := head, head
 8    for fast != nil && fast.Next != nil {
 9        slow = slow.Next
10        fast = fast.Next.Next
11    }
12    
13    // Reverse second half
14    var prev *ListNode
15    curr := slow
16    for curr != nil {
17        next := curr.Next
18        curr.Next = prev
19        prev = curr
20        curr = next
21    }
22    
23    // Merge two halves
24    first, second := head, prev
25    for second.Next != nil {
26        temp1, temp2 := first.Next, second.Next
27        first.Next = second
28        second.Next = temp1
29        first, second = temp1, temp2
30    }
31}

Time: $O(n)$, Space: $O(1)$

Summary Table

Operation	Time	Space	Technique
Find Middle	$O(n)$	$O(1)$	Slow/Fast pointers
Detect Cycle	$O(n)$	$O(1)$	Floyd's algorithm
Find Cycle Start	$O(n)$	$O(1)$	Two-phase slow/fast
Reverse	$O(n)$	$O(1)$	Three pointers
Check Palindrome	$O(n)$	$O(1)$	Find middle + reverse
Remove N-th from End	$O(n)$	$O(1)$	Two pointers with gap
Find Intersection	$O(m+n)$	$O(1)$	Two pointers
Merge Sorted	$O(m+n)$	$O(1)$	Two pointers
Compare Lists	$O(min(m,n))$	$O(1)$	Simultaneous traversal
Difference (unsorted)	$O(m \times n)$	$O(1)$	Nested traversal
Difference (sorted)	$O(m+n)$	$O(1)$	Two pointers
Intersection (sorted)	$O(m+n)$	$O(1)$	Two pointers

Key Patterns

Slow/Fast Pointers: Middle, cycle detection
Two Pointers with Gap: N-th from end
Three Pointers: Reverse list
Dummy Node: Simplify edge cases
Two-List Traversal: Merge, intersection, comparison

Related Snippets

Binary Search
Binary search is an efficient algorithm for finding a target value in a sorted …
Binary Tree
A binary tree is a tree data structure where each node has at most two children, …
General Tree
A tree is a hierarchical data structure consisting of nodes connected by edges, …
Heap Data Structure
A heap is a specialized tree-based data structure that satisfies the heap …
Heap Sort
Heap sort is a comparison-based sorting algorithm that uses a binary heap data …
LRU and LFU Cache
Cache replacement policies determine which items to evict when the cache is …
Merge Sort
Merge sort is a stable, comparison-based sorting algorithm that uses the …
Quadtree
A Quadtree is a tree data structure where each internal node has exactly four …
Quick Sort
Quick sort is an efficient, in-place, comparison-based sorting algorithm that …
String Similarity Algorithms
Algorithms for measuring similarity between strings, used in spell checking, DNA …
Terrain & Heightmap Generation
Procedural terrain generation creates realistic landscapes using mathematical …
Trie (Prefix Tree)
A Trie (pronounced "try") is a tree-like data structure used to store …
Wave Function Collapse
Wave Function Collapse (WFC) is a procedural generation algorithm that creates …