A singly linked list is a fundamental data structure where each node contains data and a reference (or pointer) to the next node in the sequence. Unlike arrays where elements are stored in contiguous memory, linked list elements can be scattered throughout memory, connected only by these pointers.
The key insight for reversing a linked list is understanding that we need to change the direction of all the pointers. In the original list, each node points to the next node in the forward direction. To reverse it, we need each node to point to the previous node instead.
The challenge is that once we change a node's next pointer, we lose our connection to the rest of the original list. This is why we need to carefully manage multiple pointers during the reversal process.
The standard approach uses three pointers: previous, current, and next. We iterate through the list, and for each node, we:
This technique of managing multiple pointers is common in many linked list algorithms. It allows us to maintain our position in the list while making modifications that would otherwise break our ability to traverse.
The beauty of this approach is that it works in-place with O(1) extra space complexity, simply by rearranging existing connections rather than creating new nodes.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6# Example: Traversing a linked list with multiple pointers
7def find_middle_node(head):
8 slow = head
9 fast = head
10
11 # Fast pointer moves 2 steps, slow moves 1 step
12 while fast and fast.next:
13 slow = slow.next # Move slow pointer one step
14 fast = fast.next.next # Move fast pointer two steps
15
16 return slow # Slow pointer is now at the middle