Complete DSA Series Part 6: Linked Lists

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Unlike arrays, linked lists don't require contiguous memory allocation, making insertions and deletions more efficient.

Comparison of array contiguous memory layout versus linked list scattered nodes connected by pointers — Arrays vs Linked Lists Memory Layout — arrays store elements contiguously while linked lists use scattered nodes connected via pointers

                            
                            Key Insight: Linked lists excel at dynamic memory allocation and \(O(1)\) insertions/deletions at known positions. However, they sacrifice \(O(1)\) random access that arrays provide.
                        

Arrays vs Linked Lists

Comparison Table

Operation	Array	Linked List
Access by Index	\(O(1)\)	\(O(n)\)
Insert at Beginning	\(O(n)\)	\(O(1)\)
Insert at End	\(O(1)\)*	\(O(n)\) / \(O(1)\)**
Insert in Middle	\(O(n)\)	\(O(n)\)***
Delete at Beginning	\(O(n)\)	\(O(1)\)
Search	\(O(n)\) / \(O(\log n)\)****	\(O(n)\)
Memory	Contiguous	Scattered + Overhead

* Amortized \(O(1)\) for dynamic arrays
** \(O(1)\) with tail pointer
*** \(O(1)\) once position is found
**** \(O(\log n)\) if sorted (binary search)

Singly Linked List

In a singly linked list, each node contains data and a pointer to the next node. The last node points to null (or None in Python).

# Singly Linked List - Node Class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Singly Linked List Implementation
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def is_empty(self):
        return self.head is None
    
    def __len__(self):
        return self.size
    
    # Insert at beginning - O(1)
    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
    
    # Insert at end - O(n)
    def insert_at_tail(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1
    
    # Insert at position - O(n)
    def insert_at_position(self, data, position):
        if position < 0 or position > self.size:
            raise IndexError("Position out of bounds")
        
        if position == 0:
            self.insert_at_head(data)
            return
        
        new_node = Node(data)
        current = self.head
        for _ in range(position - 1):
            current = current.next
        
        new_node.next = current.next
        current.next = new_node
        self.size += 1
    
    # Delete from beginning - O(1)
    def delete_from_head(self):
        if self.is_empty():
            raise IndexError("List is empty")
        
        deleted_data = self.head.data
        self.head = self.head.next
        self.size -= 1
        return deleted_data
    
    # Delete from end - O(n)
    def delete_from_tail(self):
        if self.is_empty():
            raise IndexError("List is empty")
        
        if self.head.next is None:
            return self.delete_from_head()
        
        current = self.head
        while current.next.next:
            current = current.next
        
        deleted_data = current.next.data
        current.next = None
        self.size -= 1
        return deleted_data
    
    # Delete by value - O(n)
    def delete_by_value(self, data):
        if self.is_empty():
            return False
        
        if self.head.data == data:
            self.head = self.head.next
            self.size -= 1
            return True
        
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        
        return False
    
    # Search - O(n)
    def search(self, data):
        current = self.head
        index = 0
        while current:
            if current.data == data:
                return index
            current = current.next
            index += 1
        return -1
    
    # Get element at index - O(n)
    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of bounds")
        
        current = self.head
        for _ in range(index):
            current = current.next
        return current.data
    
    # Display list
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements) + " -> None")

# Test Singly Linked List
sll = SinglyLinkedList()
sll.insert_at_tail(1)
sll.insert_at_tail(2)
sll.insert_at_tail(3)
sll.insert_at_head(0)
sll.insert_at_position(1.5, 2)

print("Singly Linked List:")
sll.display()  # 0 -> 1 -> 1.5 -> 2 -> 3 -> None

print(f"Size: {len(sll)}")
print(f"Search 2: index {sll.search(2)}")
print(f"Element at index 3: {sll.get(3)}")

sll.delete_from_head()
sll.delete_by_value(1.5)
sll.display()  # 1 -> 2 -> 3 -> None

// Singly Linked List Implementation in C++

#include <iostream>
using namespace std;

// Node class
class Node {
public:
    int data;
    Node* next;
    
    Node(int val) : data(val), next(nullptr) {}
};

// Singly Linked List class
class SinglyLinkedList {
private:
    Node* head;
    int size;

public:
    SinglyLinkedList() : head(nullptr), size(0) {}
    
    bool isEmpty() { return head == nullptr; }
    int getSize() { return size; }
    
    // Insert at head - O(1)
    void insertAtHead(int data) {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
        size++;
    }
    
    // Insert at tail - O(n)
    void insertAtTail(int data) {
        Node* newNode = new Node(data);
        if (isEmpty()) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
        size++;
    }
    
    // Insert at position - O(n)
    void insertAtPosition(int data, int position) {
        if (position < 0 || position > size) {
            throw out_of_range("Position out of bounds");
        }
        
        if (position == 0) {
            insertAtHead(data);
            return;
        }
        
        Node* newNode = new Node(data);
        Node* current = head;
        for (int i = 0; i < position - 1; i++) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
        size++;
    }
    
    // Delete from head - O(1)
    int deleteFromHead() {
        if (isEmpty()) throw runtime_error("List is empty");
        
        int deletedData = head->data;
        Node* temp = head;
        head = head->next;
        delete temp;
        size--;
        return deletedData;
    }
    
    // Delete from tail - O(n)
    int deleteFromTail() {
        if (isEmpty()) throw runtime_error("List is empty");
        
        if (head->next == nullptr) {
            return deleteFromHead();
        }
        
        Node* current = head;
        while (current->next->next) {
            current = current->next;
        }
        
        int deletedData = current->next->data;
        delete current->next;
        current->next = nullptr;
        size--;
        return deletedData;
    }
    
    // Search - O(n)
    int search(int data) {
        Node* current = head;
        int index = 0;
        while (current) {
            if (current->data == data) return index;
            current = current->next;
            index++;
        }
        return -1;
    }
    
    // Display list
    void display() {
        Node* current = head;
        while (current) {
            cout << current->data << " -> ";
            current = current->next;
        }
        cout << "None" << endl;
    }
    
    // Destructor
    ~SinglyLinkedList() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int main() {
    SinglyLinkedList sll;
    sll.insertAtTail(1);
    sll.insertAtTail(2);
    sll.insertAtTail(3);
    sll.insertAtHead(0);
    
    cout << "Singly Linked List: ";
    sll.display();  // 0 -> 1 -> 2 -> 3 -> None
    
    cout << "Size: " << sll.getSize() << endl;
    cout << "Search 2: index " << sll.search(2) << endl;
    
    sll.deleteFromHead();
    sll.display();  // 1 -> 2 -> 3 -> None
    
    return 0;
}

// Singly Linked List Implementation in Java

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SinglyLinkedList {
    private Node head;
    private int size;
    
    public SinglyLinkedList() {
        head = null;
        size = 0;
    }
    
    public boolean isEmpty() { return head == null; }
    public int getSize() { return size; }
    
    // Insert at head - O(1)
    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    // Insert at tail - O(n)
    public void insertAtTail(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }
    
    // Insert at position - O(n)
    public void insertAtPosition(int data, int position) {
        if (position < 0 || position > size) {
            throw new IndexOutOfBoundsException("Position out of bounds");
        }
        
        if (position == 0) {
            insertAtHead(data);
            return;
        }
        
        Node newNode = new Node(data);
        Node current = head;
        for (int i = 0; i < position - 1; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
        size++;
    }
    
    // Delete from head - O(1)
    public int deleteFromHead() {
        if (isEmpty()) throw new RuntimeException("List is empty");
        
        int deletedData = head.data;
        head = head.next;
        size--;
        return deletedData;
    }
    
    // Delete from tail - O(n)
    public int deleteFromTail() {
        if (isEmpty()) throw new RuntimeException("List is empty");
        
        if (head.next == null) {
            return deleteFromHead();
        }
        
        Node current = head;
        while (current.next.next != null) {
            current = current.next;
        }
        
        int deletedData = current.next.data;
        current.next = null;
        size--;
        return deletedData;
    }
    
    // Search - O(n)
    public int search(int data) {
        Node current = head;
        int index = 0;
        while (current != null) {
            if (current.data == data) return index;
            current = current.next;
            index++;
        }
        return -1;
    }
    
    // Display list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("None");
    }
    
    public static void main(String[] args) {
        SinglyLinkedList sll = new SinglyLinkedList();
        sll.insertAtTail(1);
        sll.insertAtTail(2);
        sll.insertAtTail(3);
        sll.insertAtHead(0);
        
        System.out.print("Singly Linked List: ");
        sll.display();  // 0 -> 1 -> 2 -> 3 -> None
        
        System.out.println("Size: " + sll.getSize());
        System.out.println("Search 2: index " + sll.search(2));
        
        sll.deleteFromHead();
        sll.display();  // 1 -> 2 -> 3 -> None
    }
}

Singly Linked List with Tail Pointer

The basic singly linked list has a major performance issue: appending to the end requires \(O(n)\) traversal to find the last node. Adding a tail pointer that always references the last node makes append() an \(O(1)\) operation — critical for queue implementations and any workflow that builds lists by appending. The tradeoff: you must carefully maintain the tail pointer through insertions, deletions, and edge cases (empty list, single element).

# Optimized Singly Linked List with Tail Pointer
# Insert at tail becomes O(1)

class SinglyLinkedListWithTail:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def is_empty(self):
        return self.head is None
    
    # Insert at tail - O(1) with tail pointer
    def insert_at_tail(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
    
    # Insert at head - O(1)
    def insert_at_head(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node
        self.size += 1
    
    # Delete from head - O(1)
    def delete_from_head(self):
        if self.is_empty():
            raise IndexError("List is empty")
        
        deleted_data = self.head.data
        self.head = self.head.next
        
        if self.head is None:
            self.tail = None
        
        self.size -= 1
        return deleted_data
    
    # Delete from tail - Still O(n) for singly linked
    def delete_from_tail(self):
        if self.is_empty():
            raise IndexError("List is empty")
        
        if self.head == self.tail:
            deleted_data = self.head.data
            self.head = self.tail = None
            self.size -= 1
            return deleted_data
        
        current = self.head
        while current.next != self.tail:
            current = current.next
        
        deleted_data = self.tail.data
        current.next = None
        self.tail = current
        self.size -= 1
        return deleted_data
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements) + " -> None")

# Test
sll_tail = SinglyLinkedListWithTail()
for i in range(5):
    sll_tail.insert_at_tail(i)

print("With Tail Pointer:")
sll_tail.display()  # 0 -> 1 -> 2 -> 3 -> 4 -> None

// Optimized Singly Linked List with Tail Pointer
// Insert at tail becomes O(1)

#include <iostream>
using namespace std;

class SinglyLinkedListWithTail {
private:
    Node* head;
    Node* tail;
    int size;

public:
    SinglyLinkedListWithTail() : head(nullptr), tail(nullptr), size(0) {}
    
    bool isEmpty() { return head == nullptr; }
    int getSize() { return size; }
    
    // Insert at tail - O(1) with tail pointer
    void insertAtTail(int data) {
        Node* newNode = new Node(data);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
        size++;
    }
    
    // Insert at head - O(1)
    void insertAtHead(int data) {
        Node* newNode = new Node(data);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head = newNode;
        }
        size++;
    }
    
    // Delete from head - O(1)
    int deleteFromHead() {
        if (isEmpty()) throw runtime_error("List is empty");
        
        int deletedData = head->data;
        Node* temp = head;
        head = head->next;
        delete temp;
        
        if (head == nullptr) tail = nullptr;
        
        size--;
        return deletedData;
    }
    
    // Delete from tail - Still O(n) for singly linked
    int deleteFromTail() {
        if (isEmpty()) throw runtime_error("List is empty");
        
        if (head == tail) {
            int deletedData = head->data;
            delete head;
            head = tail = nullptr;
            size--;
            return deletedData;
        }
        
        Node* current = head;
        while (current->next != tail) {
            current = current->next;
        }
        
        int deletedData = tail->data;
        delete tail;
        current->next = nullptr;
        tail = current;
        size--;
        return deletedData;
    }
    
    void display() {
        Node* current = head;
        while (current) {
            cout << current->data << " -> ";
            current = current->next;
        }
        cout << "None" << endl;
    }
    
    ~SinglyLinkedListWithTail() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int main() {
    SinglyLinkedListWithTail sll;
    for (int i = 0; i < 5; i++) {
        sll.insertAtTail(i);
    }
    
    cout << "With Tail Pointer: ";
    sll.display();  // 0 -> 1 -> 2 -> 3 -> 4 -> None
    return 0;
}

// Optimized Singly Linked List with Tail Pointer
// Insert at tail becomes O(1)

public class SinglyLinkedListWithTail {
    private Node head;
    private Node tail;
    private int size;
    
    public SinglyLinkedListWithTail() {
        head = null;
        tail = null;
        size = 0;
    }
    
    public boolean isEmpty() { return head == null; }
    public int getSize() { return size; }
    
    // Insert at tail - O(1) with tail pointer
    public void insertAtTail(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }
    
    // Insert at head - O(1)
    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
        size++;
    }
    
    // Delete from head - O(1)
    public int deleteFromHead() {
        if (isEmpty()) throw new RuntimeException("List is empty");
        
        int deletedData = head.data;
        head = head.next;
        
        if (head == null) tail = null;
        
        size--;
        return deletedData;
    }
    
    // Delete from tail - Still O(n) for singly linked
    public int deleteFromTail() {
        if (isEmpty()) throw new RuntimeException("List is empty");
        
        if (head == tail) {
            int deletedData = head.data;
            head = tail = null;
            size--;
            return deletedData;
        }
        
        Node current = head;
        while (current.next != tail) {
            current = current.next;
        }
        
        int deletedData = tail.data;
        current.next = null;
        tail = current;
        size--;
        return deletedData;
    }
    
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("None");
    }
    
    public static void main(String[] args) {
        SinglyLinkedListWithTail sll = new SinglyLinkedListWithTail();
        for (int i = 0; i < 5; i++) {
            sll.insertAtTail(i);
        }
        
        System.out.print("With Tail Pointer: ");
        sll.display();  // 0 -> 1 -> 2 -> 3 -> 4 -> None
    }
}

Doubly Linked List

In a doubly linked list, each node has pointers to both the next and previous nodes, enabling bidirectional traversal and \(O(1)\) deletion when you have a reference to the node.

# Doubly Linked List - Node Class
class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

# Doubly Linked List Implementation
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def is_empty(self):
        return self.head is None
    
    def __len__(self):
        return self.size
    
    # Insert at head - O(1)
    def insert_at_head(self, data):
        new_node = DNode(data)
        
        if self.is_empty():
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        
        self.size += 1
    
    # Insert at tail - O(1)
    def insert_at_tail(self, data):
        new_node = DNode(data)
        
        if self.is_empty():
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        
        self.size += 1
    
    # Delete node - O(1) if node reference is given
    def delete_node(self, node):
        if node is None:
            return
        
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        
        self.size -= 1
    
    # Delete from head - O(1)
    def delete_from_head(self):
        if self.is_empty():
            raise IndexError("List is empty")
        
        deleted_data = self.head.data
        self.delete_node(self.head)
        return deleted_data
    
    # Delete from tail - O(1)
    def delete_from_tail(self):
        if self.is_empty():
            raise IndexError("List is empty")
        
        deleted_data = self.tail.data
        self.delete_node(self.tail)
        return deleted_data
    
    # Display forward
    def display_forward(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print("None <-> " + " <-> ".join(elements) + " <-> None")

# Test Doubly Linked List
dll = DoublyLinkedList()
for i in range(5):
    dll.insert_at_tail(i)

print("Doubly Linked List:")
dll.display_forward()   # None <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> None

dll.delete_from_tail()
dll.delete_from_head()
dll.display_forward()   # None <-> 1 <-> 2 <-> 3 <-> None

// Doubly Linked List Implementation in C++

#include <iostream>
using namespace std;

// Doubly Linked Node
class DNode {
public:
    int data;
    DNode* prev;
    DNode* next;
    
    DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// Doubly Linked List
class DoublyLinkedList {
private:
    DNode* head;
    DNode* tail;
    int size;

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    bool isEmpty() { return head == nullptr; }
    int getSize() { return size; }
    
    // Insert at head - O(1)
    void insertAtHead(int data) {
        DNode* newNode = new DNode(data);
        
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        size++;
    }
    
    // Insert at tail - O(1)
    void insertAtTail(int data) {
        DNode* newNode = new DNode(data);
        
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
        size++;
    }
    
    // Delete node - O(1) if node reference is given
    void deleteNode(DNode* node) {
        if (node == nullptr) return;
        
        if (node->prev) {
            node->prev->next = node->next;
        } else {
            head = node->next;
        }
        
        if (node->next) {
            node->next->prev = node->prev;
        } else {
            tail = node->prev;
        }
        
        delete node;
        size--;
    }
    
    // Delete from head - O(1)
    int deleteFromHead() {
        if (isEmpty()) throw runtime_error("List is empty");
        
        int deletedData = head->data;
        deleteNode(head);
        return deletedData;
    }
    
    // Delete from tail - O(1)
    int deleteFromTail() {
        if (isEmpty()) throw runtime_error("List is empty");
        
        int deletedData = tail->data;
        deleteNode(tail);
        return deletedData;
    }
    
    // Display forward
    void displayForward() {
        cout << "None <-> ";
        DNode* current = head;
        while (current) {
            cout << current->data << " <-> ";
            current = current->next;
        }
        cout << "None" << endl;
    }
    
    // Destructor
    ~DoublyLinkedList() {
        while (head) {
            DNode* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int main() {
    DoublyLinkedList dll;
    for (int i = 0; i < 5; i++) {
        dll.insertAtTail(i);
    }
    
    cout << "Doubly Linked List: ";
    dll.displayForward();  // None <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> None
    
    dll.deleteFromTail();
    dll.deleteFromHead();
    dll.displayForward();  // None <-> 1 <-> 2 <-> 3 <-> None
    
    return 0;
}

// Doubly Linked List Implementation in Java

class DNode {
    int data;
    DNode prev;
    DNode next;
    
    DNode(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

public class DoublyLinkedList {
    private DNode head;
    private DNode tail;
    private int size;
    
    public DoublyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }
    
    public boolean isEmpty() { return head == null; }
    public int getSize() { return size; }
    
    // Insert at head - O(1)
    public void insertAtHead(int data) {
        DNode newNode = new DNode(data);
        
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }
    
    // Insert at tail - O(1)
    public void insertAtTail(int data) {
        DNode newNode = new DNode(data);
        
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }
    
    // Delete node - O(1) if node reference is given
    private void deleteNode(DNode node) {
        if (node == null) return;
        
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        
        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
        
        size--;
    }
    
    // Delete from head - O(1)
    public int deleteFromHead() {
        if (isEmpty()) throw new RuntimeException("List is empty");
        
        int deletedData = head.data;
        deleteNode(head);
        return deletedData;
    }
    
    // Delete from tail - O(1)
    public int deleteFromTail() {
        if (isEmpty()) throw new RuntimeException("List is empty");
        
        int deletedData = tail.data;
        deleteNode(tail);
        return deletedData;
    }
    
    // Display forward
    public void displayForward() {
        System.out.print("None <-> ");
        DNode current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("None");
    }
    
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        for (int i = 0; i < 5; i++) {
            dll.insertAtTail(i);
        }
        
        System.out.print("Doubly Linked List: ");
        dll.displayForward();  // None <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> None
        
        dll.deleteFromTail();
        dll.deleteFromHead();
        dll.displayForward();  // None <-> 1 <-> 2 <-> 3 <-> None
    }
}

Circular Linked List

In a circular linked list, the last node points back to the first node, creating a loop. This is useful for applications like round-robin scheduling, circular buffers, and playlists.

# Circular Singly Linked List Implementation
class CircularLinkedList:
    def __init__(self):
        self.tail = None  # Point to last node (easier operations)
        self.size = 0
    
    def is_empty(self):
        return self.tail is None
    
    # Insert at head - O(1)
    def insert_at_head(self, data):
        new_node = Node(data)
        
        if self.is_empty():
            new_node.next = new_node  # Point to itself
            self.tail = new_node
        else:
            new_node.next = self.tail.next  # Point to old head
            self.tail.next = new_node       # Tail points to new head
        
        self.size += 1
    
    # Insert at tail - O(1)
    def insert_at_tail(self, data):
        self.insert_at_head(data)
        self.tail = self.tail.next  # Move tail to new node
    
    # Delete from head - O(1)
    def delete_from_head(self):
        if self.is_empty():
            raise IndexError("List is empty")
        
        head = self.tail.next
        deleted_data = head.data
        
        if self.tail == head:  # Only one node
            self.tail = None
        else:
            self.tail.next = head.next
        
        self.size -= 1
        return deleted_data
    
    # Rotate the list (move head to tail)
    def rotate(self):
        if not self.is_empty():
            self.tail = self.tail.next
    
    # Display
    def display(self):
        if self.is_empty():
            print("Empty list")
            return
        
        elements = []
        current = self.tail.next  # Start from head
        while True:
            elements.append(str(current.data))
            current = current.next
            if current == self.tail.next:
                break
        
        print(" -> ".join(elements) + " -> (back to head)")

# Test Circular Linked List
cll = CircularLinkedList()
for i in range(1, 6):
    cll.insert_at_tail(i)

print("Circular Linked List:")
cll.display()  # 1 -> 2 -> 3 -> 4 -> 5 -> (back to head)

cll.rotate()
cll.display()  # 2 -> 3 -> 4 -> 5 -> 1 -> (back to head)

// Circular Singly Linked List Implementation in C++

#include <iostream>
using namespace std;

class CircularLinkedList {
private:
    Node* tail;
    int size;

public:
    CircularLinkedList() : tail(nullptr), size(0) {}
    
    bool isEmpty() { return tail == nullptr; }
    int getSize() { return size; }
    
    // Insert at head - O(1)
    void insertAtHead(int data) {
        Node* newNode = new Node(data);
        
        if (isEmpty()) {
            newNode->next = newNode;  // Point to itself
            tail = newNode;
        } else {
            newNode->next = tail->next;  // Point to old head
            tail->next = newNode;        // Tail points to new head
        }
        size++;
    }
    
    // Insert at tail - O(1)
    void insertAtTail(int data) {
        insertAtHead(data);
        tail = tail->next;  // Move tail to new node
    }
    
    // Delete from head - O(1)
    int deleteFromHead() {
        if (isEmpty()) throw runtime_error("List is empty");
        
        Node* head = tail->next;
        int deletedData = head->data;
        
        if (tail == head) {  // Only one node
            tail = nullptr;
        } else {
            tail->next = head->next;
        }
        
        delete head;
        size--;
        return deletedData;
    }
    
    // Rotate the list
    void rotate() {
        if (!isEmpty()) {
            tail = tail->next;
        }
    }
    
    // Display
    void display() {
        if (isEmpty()) {
            cout << "Empty list" << endl;
            return;
        }
        
        Node* current = tail->next;  // Start from head
        do {
            cout << current->data << " -> ";
            current = current->next;
        } while (current != tail->next);
        cout << "(back to head)" << endl;
    }
    
    ~CircularLinkedList() {
        if (isEmpty()) return;
        Node* current = tail->next;
        while (current != tail) {
            Node* temp = current;
            current = current->next;
            delete temp;
        }
        delete tail;
    }
};

int main() {
    CircularLinkedList cll;
    for (int i = 1; i <= 5; i++) {
        cll.insertAtTail(i);
    }
    
    cout << "Circular Linked List: ";
    cll.display();  // 1 -> 2 -> 3 -> 4 -> 5 -> (back to head)
    
    cll.rotate();
    cll.display();  // 2 -> 3 -> 4 -> 5 -> 1 -> (back to head)
    
    return 0;
}

// Circular Singly Linked List Implementation in Java

public class CircularLinkedList {
    private Node tail;
    private int size;
    
    public CircularLinkedList() {
        tail = null;
        size = 0;
    }
    
    public boolean isEmpty() { return tail == null; }
    public int getSize() { return size; }
    
    // Insert at head - O(1)
    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        
        if (isEmpty()) {
            newNode.next = newNode;  // Point to itself
            tail = newNode;
        } else {
            newNode.next = tail.next;  // Point to old head
            tail.next = newNode;       // Tail points to new head
        }
        size++;
    }
    
    // Insert at tail - O(1)
    public void insertAtTail(int data) {
        insertAtHead(data);
        tail = tail.next;  // Move tail to new node
    }
    
    // Delete from head - O(1)
    public int deleteFromHead() {
        if (isEmpty()) throw new RuntimeException("List is empty");
        
        Node head = tail.next;
        int deletedData = head.data;
        
        if (tail == head) {  // Only one node
            tail = null;
        } else {
            tail.next = head.next;
        }
        
        size--;
        return deletedData;
    }
    
    // Rotate the list
    public void rotate() {
        if (!isEmpty()) {
            tail = tail.next;
        }
    }
    
    // Display
    public void display() {
        if (isEmpty()) {
            System.out.println("Empty list");
            return;
        }
        
        Node current = tail.next;  // Start from head
        do {
            System.out.print(current.data + " -> ");
            current = current.next;
        } while (current != tail.next);
        System.out.println("(back to head)");
    }
    
    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        for (int i = 1; i <= 5; i++) {
            cll.insertAtTail(i);
        }
        
        System.out.print("Circular Linked List: ");
        cll.display();  // 1 -> 2 -> 3 -> 4 -> 5 -> (back to head)
        
        cll.rotate();
        cll.display();  // 2 -> 3 -> 4 -> 5 -> 1 -> (back to head)
    }
}

Circular Doubly Linked List

# Circular Doubly Linked List Implementation
class CircularDoublyLinkedList:
    def __init__(self):
        # Use sentinel node for cleaner code
        self.sentinel = DNode(None)
        self.sentinel.next = self.sentinel
        self.sentinel.prev = self.sentinel
        self.size = 0
    
    def is_empty(self):
        return self.sentinel.next == self.sentinel
    
    # Insert after given node - O(1)
    def _insert_after(self, node, data):
        new_node = DNode(data)
        new_node.prev = node
        new_node.next = node.next
        node.next.prev = new_node
        node.next = new_node
        self.size += 1
    
    # Insert at head - O(1)
    def insert_at_head(self, data):
        self._insert_after(self.sentinel, data)
    
    # Insert at tail - O(1)
    def insert_at_tail(self, data):
        self._insert_after(self.sentinel.prev, data)
    
    # Delete node - O(1)
    def _delete_node(self, node):
        if node == self.sentinel:
            return None
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node.data
    
    # Delete from head - O(1)
    def delete_from_head(self):
        if self.is_empty():
            raise IndexError("List is empty")
        return self._delete_node(self.sentinel.next)
    
    # Delete from tail - O(1)
    def delete_from_tail(self):
        if self.is_empty():
            raise IndexError("List is empty")
        return self._delete_node(self.sentinel.prev)
    
    # Display
    def display(self):
        elements = []
        current = self.sentinel.next
        while current != self.sentinel:
            elements.append(str(current.data))
            current = current.next
        print(" <-> ".join(elements) + " <-> (circular)")

# Test
cdll = CircularDoublyLinkedList()
for i in range(1, 6):
    cdll.insert_at_tail(i)

cdll.display()  # 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> (circular)

// Circular Doubly Linked List with Sentinel Node

#include <iostream>
using namespace std;

class CircularDoublyLinkedList {
private:
    DNode* sentinel;
    int size;
    
    void insertAfter(DNode* node, int data) {
        DNode* newNode = new DNode(data);
        newNode->prev = node;
        newNode->next = node->next;
        node->next->prev = newNode;
        node->next = newNode;
        size++;
    }
    
    int deleteNode(DNode* node) {
        if (node == sentinel) return -1;
        int data = node->data;
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete node;
        size--;
        return data;
    }

public:
    CircularDoublyLinkedList() {
        sentinel = new DNode(0);
        sentinel->next = sentinel;
        sentinel->prev = sentinel;
        size = 0;
    }
    
    bool isEmpty() { return sentinel->next == sentinel; }
    
    // Insert at head - O(1)
    void insertAtHead(int data) {
        insertAfter(sentinel, data);
    }
    
    // Insert at tail - O(1)
    void insertAtTail(int data) {
        insertAfter(sentinel->prev, data);
    }
    
    // Delete from head - O(1)
    int deleteFromHead() {
        if (isEmpty()) throw runtime_error("List is empty");
        return deleteNode(sentinel->next);
    }
    
    // Delete from tail - O(1)
    int deleteFromTail() {
        if (isEmpty()) throw runtime_error("List is empty");
        return deleteNode(sentinel->prev);
    }
    
    void display() {
        DNode* current = sentinel->next;
        while (current != sentinel) {
            cout << current->data << " <-> ";
            current = current->next;
        }
        cout << "(circular)" << endl;
    }
    
    ~CircularDoublyLinkedList() {
        while (!isEmpty()) deleteFromHead();
        delete sentinel;
    }
};

int main() {
    CircularDoublyLinkedList cdll;
    for (int i = 1; i <= 5; i++) cdll.insertAtTail(i);
    cdll.display();  // 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> (circular)
    return 0;
}

// Circular Doubly Linked List with Sentinel Node

public class CircularDoublyLinkedList {
    private DNode sentinel;
    private int size;
    
    public CircularDoublyLinkedList() {
        sentinel = new DNode(0);
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
        size = 0;
    }
    
    public boolean isEmpty() { return sentinel.next == sentinel; }
    
    private void insertAfter(DNode node, int data) {
        DNode newNode = new DNode(data);
        newNode.prev = node;
        newNode.next = node.next;
        node.next.prev = newNode;
        node.next = newNode;
        size++;
    }
    
    private int deleteNode(DNode node) {
        if (node == sentinel) return -1;
        int data = node.data;
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
        return data;
    }
    
    // Insert at head - O(1)
    public void insertAtHead(int data) {
        insertAfter(sentinel, data);
    }
    
    // Insert at tail - O(1)
    public void insertAtTail(int data) {
        insertAfter(sentinel.prev, data);
    }
    
    // Delete from head - O(1)
    public int deleteFromHead() {
        if (isEmpty()) throw new RuntimeException("List is empty");
        return deleteNode(sentinel.next);
    }
    
    // Delete from tail - O(1)
    public int deleteFromTail() {
        if (isEmpty()) throw new RuntimeException("List is empty");
        return deleteNode(sentinel.prev);
    }
    
    public void display() {
        DNode current = sentinel.next;
        while (current != sentinel) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("(circular)");
    }
    
    public static void main(String[] args) {
        CircularDoublyLinkedList cdll = new CircularDoublyLinkedList();
        for (int i = 1; i <= 5; i++) cdll.insertAtTail(i);
        cdll.display();  // 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> (circular)
    }
}

Key Techniques

List Reversal

Reversing a linked list is the single most common interview question on linked lists. The iterative three-pointer technique uses prev, current, and next: at each step, save current.next, reverse the link (current.next = prev), then advance all three pointers. After one pass, the list is reversed in \(O(n)\) time with \(O(1)\) space. The recursive approach is elegant but uses \(O(n)\) stack space.

Variations to master: Reverse between positions \(m\) and \(n\) (LeetCode 92), reverse in K-groups (LeetCode 25), and check if a list is a palindrome (reverse second half, then compare).

# Reverse Linked List - Three Approaches
# All approaches: Time O(n), Space varies

# 1. Iterative Reversal - Space O(1)
def reverse_iterative(head):
    """Reverse using three pointers"""
    prev = None
    current = head
    
    while current:
        next_node = current.next  # Save next
        current.next = prev       # Reverse link
        prev = current            # Move prev forward
        current = next_node       # Move current forward
    
    return prev  # New head

# 2. Recursive Reversal - Space O(n) call stack
def reverse_recursive(head):
    """Reverse recursively"""
    if not head or not head.next:
        return head
    
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

# 3. Reverse using Stack - Space O(n)
def reverse_with_stack(head):
    """Reverse using a stack"""
    if not head:
        return None
    
    stack = []
    current = head
    while current:
        stack.append(current)
        current = current.next
    
    new_head = stack.pop()
    current = new_head
    while stack:
        current.next = stack.pop()
        current = current.next
    current.next = None
    return new_head

# Test
original = create_list([1, 2, 3, 4, 5])
display_list(original)  # 1 -> 2 -> 3 -> 4 -> 5 -> None
reversed_list = reverse_iterative(original)
display_list(reversed_list)  # 5 -> 4 -> 3 -> 2 -> 1 -> None

// Reverse Linked List - Three Approaches

#include <iostream>
#include <stack>
using namespace std;

// 1. Iterative Reversal - O(n) time, O(1) space
ListNode* reverseIterative(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;
    
    while (current) {
        ListNode* nextNode = current->next;  // Save next
        current->next = prev;                // Reverse link
        prev = current;                      // Move prev forward
        current = nextNode;                  // Move current forward
    }
    return prev;  // New head
}

// 2. Recursive Reversal - O(n) time, O(n) space (call stack)
ListNode* reverseRecursive(ListNode* head) {
    if (!head || !head->next) return head;
    
    ListNode* newHead = reverseRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

// 3. Reverse using Stack - O(n) time, O(n) space
ListNode* reverseWithStack(ListNode* head) {
    if (!head) return nullptr;
    
    stack<ListNode*> stk;
    ListNode* current = head;
    while (current) {
        stk.push(current);
        current = current->next;
    }
    
    ListNode* newHead = stk.top();
    stk.pop();
    current = newHead;
    
    while (!stk.empty()) {
        current->next = stk.top();
        stk.pop();
        current = current->next;
    }
    current->next = nullptr;
    return newHead;
}

int main() {
    // Create: 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    head = reverseIterative(head);
    // Output: 5 -> 4 -> 3 -> 2 -> 1 -> null
    return 0;
}

// Reverse Linked List - Three Approaches

import java.util.Stack;

public class ListReversal {
    
    // 1. Iterative Reversal - O(n) time, O(1) space
    public static ListNode reverseIterative(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode nextNode = current.next;  // Save next
            current.next = prev;               // Reverse link
            prev = current;                    // Move prev forward
            current = nextNode;                // Move current forward
        }
        return prev;  // New head
    }
    
    // 2. Recursive Reversal - O(n) time, O(n) space (call stack)
    public static ListNode reverseRecursive(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode newHead = reverseRecursive(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
    
    // 3. Reverse using Stack - O(n) time, O(n) space
    public static ListNode reverseWithStack(ListNode head) {
        if (head == null) return null;
        
        Stack<ListNode> stack = new Stack<>();
        ListNode current = head;
        while (current != null) {
            stack.push(current);
            current = current.next;
        }
        
        ListNode newHead = stack.pop();
        current = newHead;
        
        while (!stack.isEmpty()) {
            current.next = stack.pop();
            current = current.next;
        }
        current.next = null;
        return newHead;
    }
    
    public static void main(String[] args) {
        // Create: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        
        head = reverseIterative(head);
        // Output: 5 -> 4 -> 3 -> 2 -> 1 -> null
    }
}

Two Pointer Techniques

The slow/fast pointer (Floyd's Tortoise and Hare) pattern is the Swiss Army knife of linked list problems. One pointer moves 1 step at a time, the other moves 2 steps. When fast reaches the end, slow is at the middle. This technique also detects cycles (if fast catches slow, there's a cycle) and finds the start of a cycle. Other two-pointer patterns: maintain a gap of K nodes between pointers to find the K-th node from the end in one pass.

# Two Pointer Techniques for Linked Lists

# 1. Find Middle Element - Floyd's Tortoise & Hare
def find_middle(head):
    """Find middle node using slow & fast pointers"""
    if not head:
        return None
    
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # Middle node

# 2. Find Nth Node from End
def find_nth_from_end(head, n):
    """Find nth node from end using two pointers"""
    first = second = head
    
    # Move first pointer n steps ahead
    for _ in range(n):
        if not first:
            return None  # n > length
        first = first.next
    
    # Move both until first reaches end
    while first:
        first = first.next
        second = second.next
    return second

# 3. Check if Palindrome
def is_palindrome(head):
    """Check if linked list is palindrome"""
    if not head or not head.next:
        return True
    
    # Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse second half
    second_half = reverse_iterative(slow.next)
    
    # Compare both halves
    first_half = head
    result = True
    while second_half:
        if first_half.data != second_half.data:
            result = False
            break
        first_half = first_half.next
        second_half = second_half.next
    return result

# Test
print(f"Middle of [1,2,3,4,5]: {find_middle(create_list([1,2,3,4,5])).data}")  # 3
print(f"2nd from end: {find_nth_from_end(create_list([1,2,3,4,5]), 2).data}")  # 4
print(f"Is [1,2,3,2,1] palindrome: {is_palindrome(create_list([1,2,3,2,1]))}")  # True

// Two Pointer Techniques for Linked Lists

#include <iostream>
using namespace std;

// 1. Find Middle Element - Floyd's Tortoise & Hare
ListNode* findMiddle(ListNode* head) {
    if (!head) return nullptr;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;  // Middle node
}

// 2. Find Nth Node from End
ListNode* findNthFromEnd(ListNode* head, int n) {
    ListNode* first = head;
    ListNode* second = head;
    
    // Move first pointer n steps ahead
    for (int i = 0; i < n; i++) {
        if (!first) return nullptr;  // n > length
        first = first->next;
    }
    
    // Move both until first reaches end
    while (first) {
        first = first->next;
        second = second->next;
    }
    return second;
}

// Helper to reverse list (for palindrome check)
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    while (head) {
        ListNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

// 3. Check if Palindrome
bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    
    // Find middle
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // Reverse second half
    ListNode* secondHalf = reverseList(slow->next);
    
    // Compare both halves
    ListNode* firstHalf = head;
    while (secondHalf) {
        if (firstHalf->val != secondHalf->val)
            return false;
        firstHalf = firstHalf->next;
        secondHalf = secondHalf->next;
    }
    return true;
}

int main() {
    // Test with 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    cout << "Middle: " << findMiddle(head)->val << endl;  // 3
    cout << "2nd from end: " << findNthFromEnd(head, 2)->val << endl;  // 4
    return 0;
}

// Two Pointer Techniques for Linked Lists

public class TwoPointerTechniques {
    
    // 1. Find Middle Element - Floyd's Tortoise & Hare
    public static ListNode findMiddle(ListNode head) {
        if (head == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;  // Middle node
    }
    
    // 2. Find Nth Node from End
    public static ListNode findNthFromEnd(ListNode head, int n) {
        ListNode first = head;
        ListNode second = head;
        
        // Move first pointer n steps ahead
        for (int i = 0; i < n; i++) {
            if (first == null) return null;  // n > length
            first = first.next;
        }
        
        // Move both until first reaches end
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        return second;
    }
    
    // Helper to reverse list
    private static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    
    // 3. Check if Palindrome
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        
        // Find middle
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Reverse second half
        ListNode secondHalf = reverseList(slow.next);
        
        // Compare both halves
        ListNode firstHalf = head;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val)
                return false;
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }
        return true;
    }
    
    public static void main(String[] args) {
        // Test with 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        
        System.out.println("Middle: " + findMiddle(head).val);  // 3
        System.out.println("2nd from end: " + findNthFromEnd(head, 2).val);  // 4
    }
}

Cycle Detection

Floyd's Cycle Detection proves mathematically that if a cycle exists, the fast pointer (2 steps) will eventually meet the slow pointer (1 step) inside the cycle. To find where the cycle starts: once they meet, reset one pointer to head and advance both at speed 1 — they'll meet exactly at the cycle's entry point. This is because the distance from head to cycle start equals the distance from the meeting point to cycle start (modulo cycle length).

Real-World Applications of Cycle Detection

Memory leak detection (circular references in garbage collectors), infinite loop detection in state machines, finding duplicates in arrays (LeetCode 287 — treat array values as "next" pointers), and deadlock detection in operating systems (resource allocation graphs with cycles).

# Cycle Detection - Floyd's Algorithm

def has_cycle(head):
    """Detect if linked list has a cycle - O(n) time, O(1) space"""
    if not head or not head.next:
        return False
    
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

def find_cycle_start(head):
    """Find the starting node of the cycle"""
    if not head or not head.next:
        return None
    
    slow = fast = head
    
    # Phase 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle
    
    # Phase 2: Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow  # Cycle start

def get_cycle_length(head):
    """Get the length of the cycle"""
    if not head or not head.next:
        return 0
    
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Count cycle length
            length = 1
            current = slow.next
            while current != slow:
                length += 1
                current = current.next
            return length
    return 0  # No cycle

# Test: Create list with cycle: 1 -> 2 -> 3 -> 4 -> 5 -> 3
nodes = [Node(i) for i in range(1, 6)]
for i in range(4):
    nodes[i].next = nodes[i + 1]
nodes[4].next = nodes[2]  # 5 -> 3 (cycle)

print(f"Has cycle: {has_cycle(nodes[0])}")           # True
print(f"Cycle starts at: {find_cycle_start(nodes[0]).data}")  # 3
print(f"Cycle length: {get_cycle_length(nodes[0])}")  # 3

// Cycle Detection - Floyd's Algorithm

#include <iostream>
using namespace std;

// Detect if linked list has a cycle - O(n) time, O(1) space
bool hasCycle(ListNode* head) {
    if (!head || !head->next) return false;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// Find the starting node of the cycle
ListNode* findCycleStart(ListNode* head) {
    if (!head || !head->next) return nullptr;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    // Phase 1: Detect cycle
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    
    if (!fast || !fast->next) return nullptr;  // No cycle
    
    // Phase 2: Find cycle start
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;  // Cycle start
}

// Get the length of the cycle
int getCycleLength(ListNode* head) {
    if (!head || !head->next) return 0;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            // Count cycle length
            int length = 1;
            ListNode* current = slow->next;
            while (current != slow) {
                length++;
                current = current->next;
            }
            return length;
        }
    }
    return 0;  // No cycle
}

int main() {
    // Create list with cycle: 1 -> 2 -> 3 -> 4 -> 5 -> 3
    ListNode* nodes[5];
    for (int i = 0; i < 5; i++) {
        nodes[i] = new ListNode(i + 1);
    }
    for (int i = 0; i < 4; i++) {
        nodes[i]->next = nodes[i + 1];
    }
    nodes[4]->next = nodes[2];  // 5 -> 3 (cycle)
    
    cout << "Has cycle: " << (hasCycle(nodes[0]) ? "true" : "false") << endl;
    cout << "Cycle starts at: " << findCycleStart(nodes[0])->val << endl;
    cout << "Cycle length: " << getCycleLength(nodes[0]) << endl;
    return 0;
}

// Cycle Detection - Floyd's Algorithm

public class CycleDetection {
    
    // Detect if linked list has a cycle - O(n) time, O(1) space
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        
        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;
    }
    
    // Find the starting node of the cycle
    public static ListNode findCycleStart(ListNode head) {
        if (head == null || head.next == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        
        // Phase 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        
        if (fast == null || fast.next == null) return null;  // No cycle
        
        // Phase 2: Find cycle start
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;  // Cycle start
    }
    
    // Get the length of the cycle
    public static int getCycleLength(ListNode head) {
        if (head == null || head.next == null) return 0;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                // Count cycle length
                int length = 1;
                ListNode current = slow.next;
                while (current != slow) {
                    length++;
                    current = current.next;
                }
                return length;
            }
        }
        return 0;  // No cycle
    }
    
    public static void main(String[] args) {
        // Create list with cycle: 1 -> 2 -> 3 -> 4 -> 5 -> 3
        ListNode[] nodes = new ListNode[5];
        for (int i = 0; i < 5; i++) {
            nodes[i] = new ListNode(i + 1);
        }
        for (int i = 0; i < 4; i++) {
            nodes[i].next = nodes[i + 1];
        }
        nodes[4].next = nodes[2];  // 5 -> 3 (cycle)
        
        System.out.println("Has cycle: " + hasCycle(nodes[0]));
        System.out.println("Cycle starts at: " + findCycleStart(nodes[0]).val);
        System.out.println("Cycle length: " + getCycleLength(nodes[0]));
    }
}

LeetCode Practice Problems

Easy 206. Reverse Linked List

Reverse a singly linked list.

# LeetCode 206 - Reverse Linked List
# Time: O(n), Space: O(1)

def reverseList(head):
    prev = None
    current = head
    
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    
    return prev

# Recursive approach
def reverseListRecursive(head):
    if not head or not head.next:
        return head
    
    new_head = reverseListRecursive(head.next)
    head.next.next = head
    head.next = None
    
    return new_head

// LeetCode 206 - Reverse Linked List
// Time: O(n), Space: O(1)

class Solution {
public:
    // Iterative approach
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* current = head;
        
        while (current) {
            ListNode* nextTemp = current->next;
            current->next = prev;
            prev = current;
            current = nextTemp;
        }
        
        return prev;
    }
    
    // Recursive approach
    ListNode* reverseListRecursive(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode* newHead = reverseListRecursive(head->next);
        head->next->next = head;
        head->next = nullptr;
        
        return newHead;
    }
};

// LeetCode 206 - Reverse Linked List
// Time: O(n), Space: O(1)

class Solution {
    // Iterative approach
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        
        return prev;
    }
    
    // Recursive approach
    public ListNode reverseListRecursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode newHead = reverseListRecursive(head.next);
        head.next.next = head;
        head.next = null;
        
        return newHead;
    }
}

Easy 21. Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list.

# LeetCode 21 - Merge Two Sorted Lists
# Time: O(n + m), Space: O(1)

def mergeTwoLists(list1, list2):
    # Create dummy head
    dummy = Node(0)
    current = dummy
    
    while list1 and list2:
        if list1.data <= list2.data:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    # Attach remaining nodes
    current.next = list1 if list1 else list2
    
    return dummy.next

// LeetCode 21 - Merge Two Sorted Lists
// Time: O(n + m), Space: O(1)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* current = &dummy;
        
        while (list1 && list2) {
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
        
        // Attach remaining nodes
        current->next = list1 ? list1 : list2;
        
        return dummy.next;
    }
};

// LeetCode 21 - Merge Two Sorted Lists
// Time: O(n + m), Space: O(1)

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        
        // Attach remaining nodes
        current.next = (list1 != null) ? list1 : list2;
        
        return dummy.next;
    }
}

Easy 141. Linked List Cycle

Determine if a linked list has a cycle.

# LeetCode 141 - Linked List Cycle
# Time: O(n), Space: O(1)

def hasCycle(head):
    if not head or not head.next:
        return False
    
    slow = head
    fast = head.next
    
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    
    return True

// LeetCode 141 - Linked List Cycle
// Time: O(n), Space: O(1)

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (!head || !head->next) return false;
        
        ListNode* slow = head;
        ListNode* fast = head->next;
        
        while (slow != fast) {
            if (!fast || !fast->next) return false;
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return true;
    }
};

// LeetCode 141 - Linked List Cycle
// Time: O(n), Space: O(1)

class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (slow != fast) {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return true;
    }
}

Medium 19. Remove Nth Node From End

Remove the nth node from the end in one pass.

# LeetCode 19 - Remove Nth Node From End
# Time: O(n), Space: O(1)

def removeNthFromEnd(head, n):
    dummy = Node(0)
    dummy.next = head
    
    first = dummy
    second = dummy
    
    # Move first n+1 steps ahead
    for _ in range(n + 1):
        first = first.next
    
    # Move both until first reaches end
    while first:
        first = first.next
        second = second.next
    
    # Remove nth node
    second.next = second.next.next
    
    return dummy.next

// LeetCode 19 - Remove Nth Node From End
// Time: O(n), Space: O(1)

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        
        ListNode* first = &dummy;
        ListNode* second = &dummy;
        
        // Move first n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            first = first->next;
        }
        
        // Move both until first reaches end
        while (first) {
            first = first->next;
            second = second->next;
        }
        
        // Remove nth node
        ListNode* toDelete = second->next;
        second->next = second->next->next;
        delete toDelete;
        
        return dummy.next;
    }
};

// LeetCode 19 - Remove Nth Node From End
// Time: O(n), Space: O(1)

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode first = dummy;
        ListNode second = dummy;
        
        // Move first n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }
        
        // Move both until first reaches end
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        
        // Remove nth node
        second.next = second.next.next;
        
        return dummy.next;
    }
}

Medium 142. Linked List Cycle II

Find the node where the cycle begins.

# LeetCode 142 - Linked List Cycle II
# Time: O(n), Space: O(1)

def detectCycle(head):
    if not head or not head.next:
        return None
    
    slow = fast = head
    
    # Phase 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            # Phase 2: Find cycle start
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    
    return None

// LeetCode 142 - Linked List Cycle II
// Time: O(n), Space: O(1)

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if (!head || !head->next) return nullptr;
        
        ListNode* slow = head;
        ListNode* fast = head;
        
        // Phase 1: Detect cycle
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                // Phase 2: Find cycle start
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        
        return nullptr;
    }
};

// LeetCode 142 - Linked List Cycle II
// Time: O(n), Space: O(1)

class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        
        // Phase 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                // Phase 2: Find cycle start
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        
        return null;
    }
}

Medium 148. Sort List

Sort a linked list in \(O(n \log n)\) time using constant space.

# LeetCode 148 - Sort List (Merge Sort)
# Time: O(n log n), Space: O(log n) for recursion

def sortList(head):
    if not head or not head.next:
        return head
    
    # Find middle
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Split list
    mid = slow.next
    slow.next = None
    
    # Recursively sort both halves
    left = sortList(head)
    right = sortList(mid)
    
    # Merge sorted halves
    return mergeTwoLists(left, right)

// LeetCode 148 - Sort List (Merge Sort)
// Time: O(n log n), Space: O(log n) for recursion

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        
        // Find middle
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // Split list
        ListNode* mid = slow->next;
        slow->next = nullptr;
        
        // Recursively sort both halves
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        
        // Merge sorted halves
        return merge(left, right);
    }
    
private:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

// LeetCode 148 - Sort List (Merge Sort)
// Time: O(n log n), Space: O(log n) for recursion

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        // Find middle
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Split list
        ListNode mid = slow.next;
        slow.next = null;
        
        // Recursively sort both halves
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        
        // Merge sorted halves
        return merge(left, right);
    }
    
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

Hard 25. Reverse Nodes in k-Group

Reverse nodes in groups of k. If remaining < k, leave as-is.

# LeetCode 25 - Reverse Nodes in k-Group
# Time: O(n), Space: O(1)

def reverseKGroup(head, k):
    # Count total nodes
    count = 0
    current = head
    while current:
        count += 1
        current = current.next
    
    dummy = Node(0)
    dummy.next = head
    group_prev = dummy
    
    while count >= k:
        # Reverse k nodes
        prev = None
        current = group_prev.next
        
        for _ in range(k):
            next_temp = current.next
            current.next = prev
            prev = current
            current = next_temp
        
        # Connect with previous group
        tail = group_prev.next  # Tail of reversed group
        tail.next = current     # Connect to remaining
        group_prev.next = prev  # Connect prev group to new head
        group_prev = tail       # Move to next group
        
        count -= k
    
    return dummy.next

// LeetCode 25 - Reverse Nodes in k-Group
// Time: O(n), Space: O(1)

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // Count total nodes
        int count = 0;
        ListNode* current = head;
        while (current) {
            count++;
            current = current->next;
        }
        
        ListNode dummy(0);
        dummy.next = head;
        ListNode* groupPrev = &dummy;
        
        while (count >= k) {
            // Reverse k nodes
            ListNode* prev = nullptr;
            current = groupPrev->next;
            
            for (int i = 0; i < k; i++) {
                ListNode* nextTemp = current->next;
                current->next = prev;
                prev = current;
                current = nextTemp;
            }
            
            // Connect with previous group
            ListNode* tail = groupPrev->next;
            tail->next = current;
            groupPrev->next = prev;
            groupPrev = tail;
            
            count -= k;
        }
        
        return dummy.next;
    }
};

// LeetCode 25 - Reverse Nodes in k-Group
// Time: O(n), Space: O(1)

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // Count total nodes
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode groupPrev = dummy;
        
        while (count >= k) {
            // Reverse k nodes
            ListNode prev = null;
            current = groupPrev.next;
            
            for (int i = 0; i < k; i++) {
                ListNode nextTemp = current.next;
                current.next = prev;
                prev = current;
                current = nextTemp;
            }
            
            // Connect with previous group
            ListNode tail = groupPrev.next;
            tail.next = current;
            groupPrev.next = prev;
            groupPrev = tail;
            
            count -= k;
        }
        
        return dummy.next;
    }
}

Next in the Series

In Part 7: Stack, we’ll use linked-list nodes to build stacks — the LIFO structure behind expression evaluation, parenthesis matching, and backtracking algorithms.

Complete DSA Series Part 6: Linked Lists

Table of Contents

FAANG Interview Prep

Foundations, Memory & Complexity

Recursion Complete Guide

Arrays & Array ADT

Strings

Matrices

Linked Lists

Stack

Queue

Trees

BST & Balanced Trees

Heaps, Sorting & Hashing

Graphs, DP, Greedy & Backtracking

Introduction to Linked Lists