Reverse Linked List
# Definition for singly-linked list
class ListNode: def __init__(self, x): self.val = x self.next = None
This problem is very basic yet IMPT. It can be solved both iteratively or recursively.
It's quite IMPT to understand and remember the steps in while loop.
def reverseList(self, head: ListNode) -> ListNode: prev = None curr = head while curr: # store next node nxt = curr.next # update next of current curr.next = prev # move prev and curr 1 step forward prev = curr curr = nxt return prev
or could combine the assignments (Python's syntactic sugar):
def reverseList(self, head: ListNode) -> ListNode: prev, curr = None, head while curr: curr.next, prev, curr = prev, curr, curr.next return prev
# Recursion (REDO)
n nodes in total. Assume to have been reversed and the
curr node is :
next to :
Also avoid the cycle by setting 's
Note that I set
curr to avoid confusion.
hd is the actual head of reversed linked list.
- space: due to implicit stack space
def reverseList(self, head: ListNode) -> ListNode: curr = head # not curr covers the empty input:  if not curr or not curr.next: return curr hd = self.reverseList(curr.next) curr.next.next = curr curr.next = None return hd