
Problem Statement
The task requires developing a solution to reverse a singly linked list. A linked list is a linear collection of data elements, where each element points to the next. Each element, or node, contains some data and a reference to the next node in the sequence. If you receive the head
of such a list, the goal is to reorient the nodes such that the head becomes the last element and the original last element becomes the first, effectively reversing the direction the nodes point. The reversed linked list should then be returned.
Examples
Example 1
Input:
head = [1,2,3,4,5]
Output:
[5,4,3,2,1]
Example 2
Input:
head = [1,2]
Output:
[2,1]
Example 3
Input:
head = []
Output:
[]
Constraints
- The number of nodes in the list is the range
[0, 5000]
. -5000 <= Node.val <= 5000
Approach and Intuition
Overview
Given the mutable nature of linked lists, we aim to reverse the internal pointers of the list without changing the data values within each node:
- Initialize three pointers:
prev
asNone
(since the new head's next should beNone
)current
as thehead
of the list (starting point)next
which will temporarily store the node next tocurrent
- Iterate through the list:
- Save the next node (i.e.,
current.next
) intonext
- Reverse the current node's pointer (i.e., point
current.next
toprev
) - Shift the
prev
andcurrent
pointers forward:prev
becomescurrent
current
moves tonext
- Save the next node (i.e.,
- At the end of the iteration,
prev
will point to the new head of the reversed list.
Detailed Steps
- If the head is
None
or if there is only one node (head.next isNone
), return head as the list is already reversed in these cases. - Utilize the three-pointer technique described above to systematically reverse the link directions from one node to the preceding node until reaching the end of the list.
- After traversing through all nodes,
prev
will point to the new head of the list sincecurrent
will beNone
when the inputs are exhausted. - Return the
prev
pointer, which now represents the head of the reversed list.
Examples Interpretation
- Example 1: Reversing [1,2,3,4,5] must provide [5,4,3,2,1]. Starting with
1
, we move each node to point to its predecessor until5
becomes the first node. - Example 2: A simple case of two elements, [1,2] becomes [2,1] by swapping the connection between the nodes.
- Example 3: An empty list simply returns an empty list, as there is nothing to reverse.
This systematic pointer adjustment method ensures that the link list is reversed in-place without utilizing additional storage, conformant with the constraints provided.
Solutions
- C++
class Solution {
public:
ListNode* reverse(ListNode* current) {
if (current == nullptr || current->next == nullptr) {
return current;
}
ListNode* reversedHead = reverse(current->next);
current->next->next = current;
current->next = nullptr;
return reversedHead;
}
};
The provided C++ code defines a solution to reverse a linked list using recursion. The function reverse
takes a pointer to a ListNode
as its parameter, which represents the current node of the linked list. This function implements the following logic:
- Base case: If the current node is
nullptr
or thenext
node of current isnullptr
, the function returns the current node. This handles the cases where the list is empty or has just one node. - Recursive step: The function recurses by calling
reverse
with the next node in the list. - Reversal logic: Upon return from the recursive call, it sets the
next
pointer of the next node to point back to the current node, effectively reversing the direction of the link. - Detachment: It then detaches the current node's
next
pointer by setting it tonullptr
to ensure the previous start of the list now becomes the end. - Completion: Once the entire list has been processed,
reversedHead
(which now points to the new head of the reversed list) is returned.
This recursive approach elegantly handles the reversal of a linked list by repositioning the links between nodes from the recursive call stack, ensuring that each node points to its predecessor, thus reversing the linked list.
- Java
class Solution {
public ListNode reverseLinkedList(ListNode start) {
if (start == null || start.next == null) {
return start;
}
ListNode newHead = reverseLinkedList(start.next);
start.next.next = start;
start.next = null;
return newHead;
}
}
This Java solution addresses the problem of reversing a linked list. The method reverseLinkedList
employs a recursive approach to invert the order of nodes in the list. Initially, the method checks if the start
node is null
or a single node by evaluating if start.next
is null
, in which case it directly returns the start
as reversing a single element or an empty list doesn't alter the list.
During each recursive call:
- The function dives to the deepest node in the list using
reverseLinkedList(start.next)
. - It sets the next node's
next
reference to point back to the currentstart
node effectively reversing the link. - It then severs the original link by setting
start.next
tonull
.
Finally, the new head of the reversed list is returned upward through the recursion stack, culminating in the original call returning the new head of the completely reversed list. This tail-end method leverages the call stack to reverse the pointers efficiently without the need for auxiliary data structures.
- Python
class Solution:
def reverseLinkedList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
newHead = self.reverseLinkedList(head.next)
head.next.next = head
head.next = None
return newHead
The Python solution provided implements the reversal of a linked list using recursion. This method focuses on handling each node in the linked list, flipping its direction, and ensuring the list remains connected appropriately.
- The function
reverseLinkedList
is a recursive function. It accepts ahead
which is the starting node of the linked list. - Check whether the
head
is null or it's the last node in the list (head.next
is null). If true, return thehead
as it represents either an empty list or the last node which will become the new head of the reversed list. - Recursively call
reverseLinkedList
with the next node of the currenthead
. This step continues until the base condition is met (reaching the end of the list). - Once reaching the end, reassign the next node's pointer, thus reversing the link. Specifically,
head.next.next = head
sets the next node's next pointer to the current node, effectively reversing the link. - Set
head.next
toNone
to break the original link and avoid cycles in the list. - Return
newHead
, the new head of the reversed list, which is obtained from the recursive calls reaching the base case.
This approach effectively reverses the linked list in-place without requiring additional data structures, relying on the call stack to handle the reversal as the recursion unwinds.
No comments yet.