Skip to main content

Linked List Approaches | Problem Solving Techniques

A Linked List is a linear data structure that allows dynamic memory management by linking elements (nodes) via pointers. This document outlines different approaches to solving problems involving linked lists, particularly focusing on iterative and recursive methods for common linked list operations.

Common Linked List Operations​

The primary operations on linked lists include:

  1. Insertion: Adding an element at the head, tail, or a specific position in the list.
  2. Deletion: Removing an element from the head, tail, or a specific position.
  3. Searching: Finding an element in the list.
  4. Traversal: Iterating through all elements in the list.

Approach 1: Iterative Approach for Linked List Operations​

Insertion at Head (Iterative)​

Inserting a new node at the head of the list involves adjusting the next pointer of the new node to point to the current head, and then updating the head pointer to the new node.

struct Node {
    int data;
    Node* next;
};

void insertAtHead(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

Approach 2: Recursive Approach for Linked List Operations​

Insertion at End (Recursive)​

Inserting at the tail can also be done recursively. Each recursive call moves one step forward until it reaches the end of the list, where the new node is appended.

void insertAtEnd(Node*& head, int value) {
    if (head == nullptr) {
        head = new Node();
        head->data = value;
        head->next = nullptr;
        return;
    }

    insertAtEnd(head->next, value);
}

Approach 3: Two Pointer Approach for Linked Lists​

The two-pointer approach, also known as the slow and fast pointer technique, is commonly used in linked list problems such as detecting cycles or finding the middle element.

Detecting Cycle in a Linked List (Floyd’s Cycle Detection)​

This approach uses two pointers: slow moves one step at a time, and fast moves two steps at a time. If there is a cycle, the two pointers will eventually meet.

bool detectCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

Approach 4: Recursive Reversal of Linked List​

Reversing a linked list recursively involves reversing the rest of the list, then fixing the head pointer.

Node* reverseRecursive(Node* head) {
    if (head == nullptr || head->next == nullptr) return head;
    
    Node* rest = reverseRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    
    return rest;
}

Time and Space Complexities​

Iterative Approach​

  • Time Complexity: O(n) for most operations, where n is the number of nodes.
  • Space Complexity: O(1) (no additional memory used).

Recursive Approach​

  • Time Complexity: O(n) for most operations.
  • Space Complexity: O(n) due to recursive stack space.

Two Pointer Approach​

  • Time Complexity: O(n) for cycle detection and finding the middle.
  • Space Complexity: O(1).

Recursive Reversal​

  • Time Complexity: O(n).
  • Space Complexity: O(n) due to recursion.