Linked Lists: definition
A singly linked list is a chain of nodes. Each node stores a value and a reference to the next node. The head identifies the first node; None marks the end. Linked-list techniques solve tasks by following and changing these links.
Problems this pattern can solve
- Reverse links without changing node values
- Merge two sorted chains
- Find the middle or detect a cycle
- Remove or rearrange nodes
Task example: Reverse Linked List
Given the first node of a singly linked list, reverse the chain and return its new first node. In this practice, reuse the original nodes and keep their values unchanged. An empty list returns None.
head = [1,2,3,4,5] result = [5,4,3,2,1]
The array notation describes node values in order, not the argument type. The editor provides ListNode with val and next. Your function receives a node or None and must return a node or None.
View LeetCode 206Stack of nodes: video explanation
head = [1,2,3,4,5] result = [5,4,3,2,1]
Prefer reading? Follow the steps below.
- Follow head to the end, saving each node reference in a Python list. Removing from the end gives the nodes in reverse order.
- Use a temporary dummy node and a tail reference. Pop a node, attach it after tail, advance tail, then set tail.next to None so an old link cannot create a cycle.
- Return dummy.next. The dummy is not part of the result. Empty input returns None; one node returns that same node.
Time complexity · O(n)
Each of n nodes is collected once and popped once. Total work is O(n).
Space complexity · O(n)
The stack stores n node references. The dummy and tail use constant additional space.
In-place reversal: video explanation
head = [1,2,3,4,5] result = [5,4,3,2,1]
Prefer reading? Follow the steps below.
- Start with prev = None and curr = head. prev marks the reversed chain; curr marks the next node to process.
- Save nxt = curr.next before changing the link. Then set curr.next = prev. Saving nxt keeps the rest of the original chain reachable.
- Move prev to curr and curr to nxt. Repeat until curr is None, then return prev as the new head.
Both approaches take linear time. Reversing links directly removes the O(n) stack and reduces extra space to O(1).
Time complexity · O(n)
Process each node once with a fixed amount of work: O(n) time.
Space complexity · O(1)
Only prev, curr, and nxt are needed, regardless of list length: O(1) extra space.