206. Reverse Linked List
Model: qwen2.5-coder:14b
Topics: Linked List
FAANG asked: 1
Acceptance rate: 65.7%
Problem Breakdown
The problem requires reversing a singly linked list given its head node. The input is the head of the linked list, and the output should be the head of the reversed linked list. The constraints indicate that the number of nodes in the list can range from 0 to 5000, with each node’s value ranging from -5000 to 5000.
Key edge cases include:
- An empty list (head is
None). - A single-node list.
- Lists with duplicate values.
Intuition
A brute-force approach would involve creating a new linked list and inserting nodes at the beginning. However, this requires additional space proportional to the number of nodes, making it inefficient in terms of both time and space complexity.
The key insight is to reverse the links between nodes in place. This can be done iteratively or recursively. The iterative approach involves maintaining three pointers: prev, current, and next. By iterating through the list and adjusting these pointers, we can reverse the links without using extra space.
Approach
We will implement both iterative and recursive solutions for reversing a linked list.
Iterative Approach:
- Initialize three pointers:
prevasNone,currentashead, andnextasNone. - Iterate through the list until
currentbecomesNone. - In each iteration, set
nexttocurrent.next, then reverse the link by settingcurrent.nexttoprev. - Move
prevtocurrentandcurrenttonext. - After the loop,
prevwill be pointing to the new head of the reversed list.
Recursive Approach:
- Base case: If
headisNoneorhead.nextisNone, returnhead. - Recursively call the function on
head.nextto reverse the rest of the list. - Adjust the links by setting
head.next.nexttoheadandhead.nexttoNone. - Return the new head obtained from the recursive call.
Complexity Analysis
- Time Complexity: O(n) for both iterative and recursive approaches, where n is the number of nodes in the linked list.
- Space Complexity: O(1) for the iterative approach (constant space). For the recursive approach, the space complexity is O(n) due to the call stack.
Solution
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# Iterative Approach
def reverseListIterative(self, head: ListNode) -> ListNode:
prev = None
current = head
while current:
next_node = current.next # Store next node
current.next = prev # Reverse current node's pointer
prev = current # Move pointers one position ahead
current = next_node
return prev
# Recursive Approach
def reverseListRecursive(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
new_head = self.reverseListRecursive(head.next)
head.next.next = head
head.next = None
return new_head
Edge Cases Handled
- Empty List: Both functions handle an empty list by returning
None. - Single Node List: The iterative approach naturally handles this case, while the recursive approach returns the single node as is.
- Lists with Duplicate Values: The reversal process does not depend on the values of the nodes, so duplicates are handled correctly.