Linked Lists Cheatsheet

REFERENCE v1.0

Linked Lists Quick Reference

Everything you need day‑to‑day – operations, algorithms, and patterns.

Types of Linked Lists

Singly Linked List

Each node stores data and a next pointer
Traversal only forward
Memory efficient (one pointer per node)

Doubly Linked List

Each node stores data, next, and prev pointers
Traversal both forward and backward
More memory (two pointers per node)

Circular Linked List

Last node points to the head (not null)
Can be singly or doubly circular
Useful for round‑robin scheduling

Advantages over Arrays

Dynamic size (no resizing needed)
Efficient insertions/deletions (O(1) at head)
No shifting of elements

Node Structure

Singly

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

Doubly

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

Basic Operations

Traversal

void traverse(ListNode head) {
    ListNode curr = head;
    while (curr != null) {
        System.out.print(curr.val + " ");
        curr = curr.next;
    }
}

Search

boolean search(ListNode head, int target) {
    ListNode curr = head;
    while (curr != null) {
        if (curr.val == target) return true;
        curr = curr.next;
    }
    return false;
}

Length

int length(ListNode head) {
    int count = 0;
    ListNode curr = head;
    while (curr != null) {
        count++;
        curr = curr.next;
    }
    return count;
}

Insert at Head

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

Insert at Tail

ListNode insertAtTail(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    if (head == null) return newNode;
    ListNode curr = head;
    while (curr.next != null) curr = curr.next;
    curr.next = newNode;
    return head;
}

Insert at Position

ListNode insertAtPosition(ListNode head, int val, int pos) {
    if (pos == 0) return insertAtHead(head, val);
    ListNode newNode = new ListNode(val);
    ListNode curr = head;
    for (int i = 0; i < pos - 1 && curr != null; i++) {
        curr = curr.next;
    }
    if (curr == null) return head;
    newNode.next = curr.next;
    curr.next = newNode;
    return head;
}

Delete at Head

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

Delete at Tail

ListNode deleteAtTail(ListNode head) {
    if (head == null || head.next == null) return null;
    ListNode curr = head;
    while (curr.next.next != null) curr = curr.next;
    curr.next = null;
    return head;
}

Delete by Value

ListNode deleteByValue(ListNode head, int val) {
    if (head == null) return null;
    if (head.val == val) return head.next;
    ListNode curr = head;
    while (curr.next != null && curr.next.val != val) {
        curr = curr.next;
    }
    if (curr.next != null) curr.next = curr.next.next;
    return head;
}

Common Algorithms

Reverse Linked List

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

// Recursive
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;
}

Detect Cycle (Floyd's Tortoise & Hare)

boolean hasCycle(ListNode head) {
    if (head == 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 Cycle Start

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

Find Middle

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;
}

Merge Two Sorted Lists

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Find Intersection of Two Lists

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    return a;
}

Remove Nth Node from End

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode slow = dummy, fast = dummy;
    for (int i = 0; i <= n; i++) fast = fast.next;
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

Palindrome Check

boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode second = reverse(slow);
    ListNode first = head;
    while (second != null) {
        if (first.val != second.val) return false;
        first = first.next;
        second = second.next;
    }
    return true;
}

Rotate List

ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null) return head;
    int len = 1;
    ListNode tail = head;
    while (tail.next != null) {
        tail = tail.next;
        len++;
    }
    k = k % len;
    if (k == 0) return head;
    tail.next = head;
    for (int i = 0; i < len - k; i++) {
        tail = tail.next;
    }
    ListNode newHead = tail.next;
    tail.next = null;
    return newHead;
}

Reorder List

void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode second = reverse(slow);
    ListNode first = head;
    while (second.next != null) {
        ListNode tmp1 = first.next;
        ListNode tmp2 = second.next;
        first.next = second;
        second.next = tmp1;
        first = tmp1;
        second = tmp2;
    }
}

Doubly Linked List Operations

Insert at Head

ListNode insertAtHeadDLL(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    if (head != null) head.prev = newNode;
    newNode.next = head;
    return newNode;
}

Insert at Tail

ListNode insertAtTailDLL(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    if (head == null) return newNode;
    ListNode curr = head;
    while (curr.next != null) curr = curr.next;
    curr.next = newNode;
    newNode.prev = curr;
    return head;
}

Delete Node

void deleteNodeDLL(ListNode node) {
    if (node.prev != null) node.prev.next = node.next;
    if (node.next != null) node.next.prev = node.prev;
}

Common Problems

Easy

Reverse Linked List
Merge Two Sorted Lists
Remove Duplicates from Sorted List
Linked List Cycle
Intersection of Two Linked Lists
Middle of Linked List

Medium

Remove Nth Node From End
Swap Nodes in Pairs
Add Two Numbers
Reorder List
LRU Cache
Palindrome Linked List

Hard

Merge K Sorted Lists
Reverse Nodes in k‑Group
Copy List with Random Pointer
LFU Cache
Sort List
Flatten Multilevel DLL

Complexities Summary

Operation	Singly (Time)	Doubly (Time)	Space
Access (by index)	O(n)	O(n)	O(1)
Search	O(n)	O(n)	O(1)
Insert at Head	O(1)	O(1)	O(1)
Insert at Tail	O(1)*	O(1)	O(1)
Insert at Middle	O(n)	O(n)	O(1)
Delete at Head	O(1)	O(1)	O(1)
Delete at Tail	O(1)*	O(1)	O(1)
Delete at Middle	O(n)	O(n)	O(1)

* With a tail pointer (O(1) for insertion/deletion at tail)

Patterns & Tips

Dummy node – use a sentinel node to simplify edge cases (insertion/deletion at head).
Two pointers – use fast/slow pointers for cycle detection, middle, nth from end.
Recursion – use for reverse, merge, and palindrome checks (stack space O(n)).
In‑place modification – most list problems can be solved in O(1) extra space.
Cycle detection – Floyd's algorithm is the standard O(n) time, O(1) space solution.
Merge – always use a dummy head for merging lists.
Edge cases – always check for null head, single node, and two nodes.

📌 Quick Reference

Reverse: prev, curr, next pointers
Cycle: slow, fast pointers
Middle: slow = head, fast = head
Nth from end: slow, fast with gap
Dummy node: ListNode dummy = new ListNode(0)

← Back to All Cheatsheets