This is one of the famous interview question - can be solved iteratively and recursively. It becomes tricky, as in LinkedList we can go in forward direction. So, we need to understand some pointer basics when traversing and reversing the list.
classSolution:
defreverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev: Optional[ListNode] =None curr: Optional[ListNode] = head
# Traversing the listwhile curr:
nxt: Optional[ListNode] = curr.next # Backup reference to the next node curr.next = prev # Reverse the link prev = curr # Move prev to the current node curr = nxt # Move curr to the next nodereturn prev
Method 2 - Recursive Approach Passing 2 Pointers to Function#
Another way is we can take 2 pointers - current ascurr and previous as prev. In each recursive call, we will keep on updating curr to curr.next, and prev as well. At the end of recursion, we will set curr.next = prev.
classSolution {
public ListNode reverseList(ListNode head) {
// Edge case: Empty listif (head ==null) {
returnnull;
}
// Call the recursive helper functionreturn helper(null, head);
}
protected ListNode helper(ListNode prev, ListNode curr) {
// Base case: If curr becomes null, prev is the new head of the reversed listif (curr ==null) {
return prev;
}
// Backup the next node before breaking the link ListNode next = curr.next;
// Reverse the link curr.next= prev;
// Recur for the rest of the listreturn helper(curr, next);
}
}
classSolution:
defreverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Edge case: Empty listifnot head:
returnNone# Start the recursive process with prev = None and curr = headreturn self._helper(None, head)
def_helper(self, prev: Optional[ListNode], curr: Optional[ListNode]) -> Optional[ListNode]:
# Base case: If curr is None, prev is the new headifnot curr:
return prev
# Backup the next node before breaking the link nxt = curr.next
# Reverse the current node's link curr.next = prev
# Recur for the rest of the listreturn self._helper(curr, nxt)
The following are the sequence of steps to be followed:
If the list is empty, then the reverse of the list is also empty
If the list has one element, then the reverse of the list is the element itself
If the list has n elements, then the reverse of the complete list is reverse of the list starting from second node followed by the first node element. This step is recursive step
classSolution {
public ListNode reverseList(ListNode head) {
// Base case: if the list is empty or has only one node, return the headif (head ==null|| head.next==null) {
return head;
}
// Recursive call to reverse the rest of the list ListNode newHead = reverseList(head.next);
// Reverse the link head.next.next= head;
head.next=null;
// Return the head of the reversed listreturn newHead;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defreverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Base case: if the list is empty or has only one node, return the headifnot head ornot head.next:
return head
# Recursive call to reverse the rest of the list new_head = self.reverseList(head.next)
# Reverse the link head.next.next = head
head.next =None# Return the head of the reversed listreturn new_head