Linked List: Master the Fundamentals

Linked lists are a fundamental data structure where elements are connected via pointers. They appear frequently in coding interviews and form the basis for more complex structures like trees and graphs.

This guide covers the main linked-list patterns and concepts. Each concept links to a detailed page with explanations and practice problems.

What Is a Linked List?

A singly linked list is a sequence of nodes; each node holds a value and a next pointer. A doubly linked list adds a prev pointer. Unlike arrays, there is no O(1) index access—you traverse by following pointers.

Key characteristics:

• Sequential access — traverse from head (and optionally tail in doubly linked)
• Dynamic size — no fixed capacity
• Pointer manipulation — insert/delete by rewiring next (and prev)
• No random access — finding the k-th node is O(k)

Core Techniques

1. Dummy Head / Sentinel Node

Using a dummy head (sentinel node) before the real head simplifies edge cases: no special handling for empty list or operations at the head.

Learn more: Dummy Head / Sentinel Node →

2. Fast and Slow Pointers (Floyd)

Fast and slow pointers (e.g. one moves 1 step, the other 2) are used for cycle detection, finding the middle node, and similar problems.

Learn more: Fast and Slow Pointers (Floyd) →

3. Reversing a Linked List (In-Place)

Reverse in-place by rewiring next pointers as you traverse. A classic interview problem and building block for others.

Learn more: Reversing a Linked List (In-Place) →

4. Merging Two Sorted Lists

Merge two sorted lists into one sorted list by comparing heads and advancing. Foundation for merge sort on linked lists.

Learn more: Merging Two Sorted Lists →

5. Cycle Detection (Floyd's Algorithm)

Cycle detection determines if a list has a cycle using fast/slow pointers (Floyd's cycle-finding algorithm).

Learn more: Cycle Detection (Floyd's Algorithm) →

6. Finding the Middle Node

Find the middle using slow (1 step) and fast (2 steps) pointers; when fast reaches the end, slow is at the middle.

Learn more: Finding the Middle Node →

7. Remove Nth Node From End

Remove the nth node from the end in one pass using two pointers: advance one by n steps, then move both until the leading pointer reaches the end.

Learn more: Remove Nth Node From End →

8. Intersection of Two Linked Lists

Intersection of two lists — find the first common node (if any). Approaches include hashing or aligning lengths then stepping together.

Learn more: Intersection of Two Linked Lists →

9. Doubly Linked List

Doubly linked lists have prev and next, enabling O(1) deletion of a known node and easier reverse traversal.

Learn more: Doubly Linked List →

Pattern-Based Problems

10. Palindrome Linked List

Palindrome linked list — check if the list reads the same forward and backward. Often solved by finding the middle, reversing the second half, and comparing.

Learn more: Palindrome Linked List →

11. Add Two Numbers (List Representation)

Add two numbers represented as linked lists (digits in reverse order). Simulate digit-by-digit addition with a carry.

Learn more: Add Two Numbers (List Representation) →

12. Reorder List (Half Reverse, Merge)

Reorder list — e.g. L0 → Ln → L1 → Ln−1 → … Combine finding the middle, reversing the second half, and merging two lists.

Learn more: Reorder List (Half Reverse, Merge) →

13. Swap Nodes in Pairs

Swap nodes in pairs — swap every two adjacent nodes. Use a dummy head and careful pointer updates.

Learn more: Swap Nodes in Pairs →

14. Reverse Nodes in K-Group

Reverse nodes in k-group — reverse every k consecutive nodes. Extend the in-place reverse pattern to fixed-size segments.

Learn more: Reverse Nodes in K-Group →

15. Merge K Sorted Lists

Merge k sorted lists into one. Use a min-heap of head nodes or merge in pairs (divide and conquer).

Learn more: Merge K Sorted Lists →

16. Copy List with Random Pointer

Copy list with random pointer — deep copy a list where each node has an extra random pointer. Typically done with a map or in-place interleaving.

Learn more: Copy List with Random Pointer →

17. Partition List

Partition list — rearrange so all nodes less than a value come before nodes greater than or equal (e.g. quick sort partition).

Learn more: Partition List →

18. Sort List (Merge Sort on List)

Sort list in O(n log n) time and O(1) space (excluding recursion). Use merge sort: find middle, sort halves, merge.

Learn more: Sort List (Merge Sort on List) →

19. Odd Even Linked List

Odd even linked list — group nodes at odd indices then even indices. Single pass with two dummy heads.

Learn more: Odd Even Linked List →

20. Delete Node Without Head Reference

Delete node when you don't have the head — copy the next node's value into the current node and skip the next node.

Learn more: Delete Node Without Head Reference →

21. Flatten a Multilevel Doubly Linked List

Flatten multilevel doubly linked list — flatten a list that has child pointers so the result is a single-level doubly linked list.

Learn more: Flatten a Multilevel Doubly Linked List →

22. Design Linked List (Implementation)

Design linked list — implement get, addAtHead, addAtTail, addAtIndex, deleteAtIndex. Good practice for pointer handling and edge cases.

Learn more: Design Linked List (Implementation) →

Learning Path

Start with: Dummy Head, Reverse In-Place, Fast and Slow Pointers.

Then: Merge Two Sorted, Cycle Detection, Find Middle, Remove Nth From End.

Advanced: Reorder List, Reverse Nodes in K-Group, Sort List, Copy List with Random Pointer.

Summary

Linked list problems rely on dummy head, fast/slow pointers, in-place reverse, and merge patterns. Use the concept links above to dive into each topic and practice.