Linked List Techniques

Generated on 2025-07-10 02:10:09 Algorithm Cheatsheet for Technical Interviews

Linked List Techniques Cheatsheet

1. Quick Overview

What is it? A linear data structure where elements (nodes) are linked using pointers. Each node contains data and a pointer to the next node (singly linked list) or both the next and previous nodes (doubly linked list).
When to use it?
- Dynamic data storage (size can change during runtime).
- Insertion and deletion at arbitrary positions are frequent operations.
- When random access is not a requirement.
- Implementing stacks, queues, graphs.
When not to use it? When frequent random access is needed (use arrays instead).

2. Time & Space Complexity

Operation	Singly Linked List	Doubly Linked List
Access	O(n)	O(n)
Search	O(n)	O(n)
Insertion (at head)	O(1)	O(1)
Insertion (at tail)	O(n) (without tail pointer), O(1) (with tail pointer)	O(1)
Deletion (at head)	O(1)	O(1)
Deletion (at tail)	O(n)	O(1)
Space Complexity	O(n)	O(n)

3. Implementation

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Example: Creating a linked list
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

# Traversing the list
def print_list(head):
    curr = head
    while curr:
        print(curr.val, end=" -> ")
        curr = curr.next
    print("None")

print_list(head) # Output: 1 -> 2 -> 3 -> None

#Insertion at head
def insert_at_head(head,val):
    newNode = ListNode(val)
    newNode.next = head
    return newNode

head = insert_at_head(head,0)
print_list(head) # Output: 0 -> 1 -> 2 -> 3 -> None

#Deletion at head
def delete_at_head(head):
    if not head:
        return None
    return head.next

head = delete_at_head(head)
print_list(head) # Output: 1 -> 2 -> 3 -> None

Java

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

// Example: Creating a linked list
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

// Traversing the list
void printList(ListNode head) {
    ListNode curr = head;
    while (curr != null) {
        System.out.print(curr.val + " -> ");
        curr = curr.next;
    }
    System.out.println("null");
}

//Insertion at head
ListNode insertAtHead(ListNode head,int val){
    ListNode newNode = new ListNode(val);
    newNode.next = head;
    return newNode;
}

//Deletion at head
ListNode deleteAtHead(ListNode head){
    if(head == null){
        return null;
    }
    return head.next;
}

C++

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// Example: Creating a linked list
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);

// Traversing the list
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != nullptr) {
        std::cout << curr->val << " -> ";
        curr = curr->next;
    }
    std::cout << "nullptr" << std::endl;
}

//Insertion at head
ListNode* insertAtHead(ListNode* head, int val){
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    return newNode;
}

//Deletion at head
ListNode* deleteAtHead(ListNode* head){
    if(head == nullptr){
        return nullptr;
    }
    return head->next;
}

4. Common Patterns

Two Pointers:
- Fast & Slow Pointers (Tortoise and Hare): Detect cycles, find middle element.
- Multiple Pointers: Compare elements, reverse a list.
Dummy Node: Simplify edge cases (e.g., insertion at the head, deletion of the head).
Recursion: Solve problems like reversing a list, merging sorted lists.
Reversal: Reverse the list in place or create a new reversed list.

5. Pro Tips

Dummy Node: Always consider using a dummy node to avoid special case handling for the head.
Memory Management (C++): Remember to delete allocated memory to prevent memory leaks.
Null Checks: Always check for null pointers before accessing their val or next fields.
Loop Invariants: Maintain clear loop invariants to ensure the correctness of your algorithms.
Draw Diagrams: Visualizing the linked list and pointer movements can significantly aid understanding and debugging.
Tail Pointer: If you need frequent insertions at the tail, maintain a tail pointer to improve performance.

6. Practice Problems

Reverse Linked List (LeetCode 206): Reverse a singly linked list.
Middle of the Linked List (LeetCode 876): Find the middle node of a linked list.
Merge Two Sorted Lists (LeetCode 21): Merge two sorted linked lists into one sorted list.
Linked List Cycle (LeetCode 141): Detect if a linked list has a cycle.

7. Templates

7.1 Reverse Linked List

Python

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

Java

ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextNode = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextNode;
    }
    return prev;
}

C++

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* nextNode = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextNode;
    }
    return prev;
}

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(1).

7.2 Find Middle Node

Python

def middleNode(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Java

ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

C++

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(1).

7.3 Merge Two Sorted Lists

Python

def mergeTwoLists(list1, list2):
    dummy = ListNode()
    tail = dummy
    while list1 and list2:
        if list1.val < list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    if list1:
        tail.next = list1
    elif list2:
        tail.next = list2
    return dummy.next

Java

ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode();
    ListNode tail = dummy;
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }
    if (list1 != null) {
        tail.next = list1;
    } else {
        tail.next = list2;
    }
    return dummy.next;
}

C++

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* dummy = new ListNode();
    ListNode* tail = dummy;
    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    if (list1 != nullptr) {
        tail->next = list1;
    } else {
        tail->next = list2;
    }
    return dummy->next;
}

Complexity Analysis

Time Complexity: O(m+n), where m and n are the number of nodes in list1 and list2 respectively.
Space Complexity: O(1).

This comprehensive cheatsheet provides a solid foundation for understanding and applying linked list techniques. Remember to practice with various problems to solidify your knowledge. Good luck!