🔄 Singly Linked List Advanced Operations

Welcome back! You now know the basics of singly linked lists. Let’s dive into advanced operations that will make you a linked list expert. These techniques are used in interviews and real-world applications!

Advanced Operations Overview

We’ll cover:

• Reversing the entire list
• Finding the middle element
• Detecting cycles (loops in the chain)
• Merging two sorted lists
• Complex real-world examples

1. Reverse the Chain

Imagine you have a line of people: Alice → Bob → Charlie → David After reversing: David → Charlie → Bob → Alice

How Reverse Works

func (ll *LinkedList) reverse() {
    var previous *Node
    current := ll.head
    var next *Node

    for current != nil {
        next = current.next      // Remember next person
        current.next = previous  // Point backwards
        previous = current       // Move previous forward
        current = next           // Move current forward
    }

    ll.head = previous  // New first person
}

// Example
list := &LinkedList{}
list.addToEnd(10)
list.addToEnd(20)
list.addToEnd(30)
// List: 10 -> 20 -> 30

list.reverse()
// List: 30 -> 20 -> 10

Visual walkthrough:

• Start: 10 -> 20 -> 30
• Step 1: 10 <- 20 -> 30 (reverse first connection)
• Step 2: 10 <- 20 <- 30 (reverse second connection)
• Result: 30 -> 20 -> 10 (head becomes 30)

2. Find the Middle Item

Challenge: Find the middle element in a linked list of unknown length.

Trick: Use two pointers - one slow, one fast!

func (ll *LinkedList) findMiddle() int {
    if ll.head == nil {
        return -1
    }

    // Two pointers: slow and fast
    slow := ll.head  // Moves one step
    fast := ll.head  // Moves two steps

    for fast != nil && fast.next != nil {
        slow = slow.next      // One step
        fast = fast.next.next // Two steps
    }

    return slow.data  // Slow reaches middle
}

// Example: 1 -> 2 -> 3 -> 4 -> 5
// Middle is 3

Why this works:

• When fast reaches end, slow is at middle
• Works for both odd and even lengths
• O(n) time, O(1) space

3. Cycle Detection - Finding Loops

Problem: Does this linked list have a cycle (loop)?

Imagine: A → B → C → A (C points back to A - infinite loop!)

Floyd’s Cycle Detection Algorithm

func (ll *LinkedList) hasCycle() bool {
    if ll.head == nil {
        return false
    }

    slow := ll.head
    fast := ll.head

    for fast != nil && fast.next != nil {
        slow = slow.next          // Move one step
        fast = fast.next.next     // Move two steps

        if slow == fast {
            return true  // Cycle detected!
        }
    }

    return false
}

// Example cycle: A -> B -> C -> A
// Slow: A -> B -> C
// Fast: A -> C -> B
// They meet at B!

Why it works:

• If there’s a cycle, fast will eventually catch slow
• Like two runners on a circular track
• O(n) time, O(1) space

Find Cycle Start Point

func (ll *LinkedList) findCycleStart() *Node {
    // First detect cycle
    slow := ll.head
    fast := ll.head

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

        if slow == fast {
            // Cycle found! Find start
            slow = ll.head
            for slow != fast {
                slow = slow.next
                fast = fast.next
            }
            return slow  // Start of cycle
        }
    }

    return nil  // No cycle
}

4. Merge Two Sorted Lists

Problem: Combine two sorted linked lists into one sorted list.

func mergeTwoLists(list1, list2 *LinkedList) *LinkedList {
    dummy := &Node{data: 0}
    current := dummy

    p1 := list1.head
    p2 := list2.head

    // Compare and merge
    for p1 != nil && p2 != nil {
        if p1.data <= p2.data {
            current.next = p1
            p1 = p1.next
        } else {
            current.next = p2
            p2 = p2.next
        }
        current = current.next
    }

    // Add remaining elements
    if p1 != nil {
        current.next = p1
    }
    if p2 != nil {
        current.next = p2
    }

    result := &LinkedList{head: dummy.next}
    result.size = list1.size + list2.size
    return result
}

// Example:
// List1: 1 -> 3 -> 5
// List2: 2 -> 4 -> 6
// Result: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Real Life Example: Browser History

package main

import "fmt"

type HistoryPage struct {
    url   string
    next  *HistoryPage
}

type BrowserHistory struct {
    current *HistoryPage
}

func (bh *BrowserHistory) visit(url string) {
    newPage := &HistoryPage{url: url, next: bh.current}
    bh.current = newPage
}

func (bh *BrowserHistory) back() string {
    if bh.current == nil {
        return "No history"
    }

    url := bh.current.url
    bh.current = bh.current.next
    return url
}

func (bh *BrowserHistory) showHistory() {
    current := bh.current
    fmt.Println("Browser History (newest first):")

    for current != nil {
        fmt.Printf("- %s\n", current.url)
        current = current.next
    }
}

func main() {
    history := &BrowserHistory{}

    history.visit("google.com")
    history.visit("github.com")
    history.visit("stackoverflow.com")

    history.showHistory()

    fmt.Println("Going back:", history.back())
    fmt.Println("Going back:", history.back())
}

Advanced Algorithm: Remove Nth from End

Problem: Remove the Nth node from the end of the list.

func (ll *LinkedList) removeNthFromEnd(n int) {
    if ll.head == nil || n <= 0 {
        return
    }

    // Use two pointers with gap of n
    dummy := &Node{data: 0, next: ll.head}
    fast := dummy
    slow := dummy

    // Move fast n+1 steps ahead
    for i := 0; i <= n; i++ {
        if fast == nil {
            return  // n is too large
        }
        fast = fast.next
    }

    // Move both pointers until fast reaches end
    for fast != nil {
        fast = fast.next
        slow = slow.next
    }

    // Remove the node
    slow.next = slow.next.next
    ll.size--
}

// Example: 1 -> 2 -> 3 -> 4 -> 5, n=2
// Remove 4th node from start (2nd from end)
// Result: 1 -> 2 -> 3 -> 5

Advanced Algorithm: Palindrome Check

Problem: Is the linked list a palindrome? (reads same forward and backward)

func (ll *LinkedList) isPalindrome() bool {
    if ll.head == nil {
        return true
    }

    // Find middle
    slow := ll.head
    fast := ll.head

    for fast != nil && fast.next != nil {
        slow = slow.next
        fast = fast.next.next
    }

    // Reverse second half
    secondHalf := reverseList(slow)

    // Compare first half with reversed second half
    firstHalf := ll.head
    result := true

    for secondHalf != nil {
        if firstHalf.data != secondHalf.data {
            result = false
            break
        }
        firstHalf = firstHalf.next
        secondHalf = secondHalf.next
    }

    return result
}

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

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

    return prev
}

// Example: 1 -> 2 -> 3 -> 2 -> 1
// Is palindrome: true

Performance Analysis

Practice Challenges - Level Up!

Challenge 1: Rotate List

Rotate a linked list to the right by k places.

Challenge 2: Intersection Point

Find if two linked lists intersect and return the intersection node.

Challenge 3: Add Two Numbers

Given two linked lists representing numbers, add them together.

Challenge 4: Reorder List

Reorder the list so that: L1 → Ln → L2 → Ln-1 → L3 → Ln-2…

Challenge 5: Copy List with Random Pointers

Each node has a random pointer. Create a deep copy.

Common Interview Questions

Question 1: Why use two pointers?

Answer: Two pointers (slow/fast) help solve problems in O(n) time with O(1) space, like finding middle or detecting cycles.

Question 2: How to reverse in place?

Answer: Use three pointers (previous, current, next) to reverse links without extra space.

Question 3: Cycle detection complexity?

Answer: O(n) time, O(1) space using Floyd’s algorithm.

Real-World Applications

1. LRU Cache - Least Recently Used

• Remove oldest items when cache is full
• Add new items to front, remove from end

2. Undo/Redo Systems

• Each action is a node in the list
• Undo: move backward, Redo: move forward

3. Music Playlists

• Add songs to end, play from front
• Skip tracks, go to previous

4. Memory Management

• Detect memory leaks (cycles)
• Garbage collection algorithms

Key Takeaways - Advanced Mastery

• Two pointers solve many linked list problems efficiently
• Cycle detection prevents infinite loops in real applications
• Reversing is fundamental for many algorithms
• Merging is key for sorting and combining data
• Middle finding enables binary search-like operations

Next: Discover doubly linked lists - where you can move in both directions! 🔄

Ready to move in both directions? Let’s explore doubly linked lists! 🚀