LC 206 - Reverse Linked List

Question

Given the head of a singly linked list, reverse the list, and return the reversed list.

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

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Links

Question here and solution here

Solution

concept

iterative

recursive

For NeetCode solution: if the example linked list is [1, 2, 3, 4, 5] In the recursive call, the deepest layer returns head = ListNode{val: 5, next: None} or [5] From the next layer up of the recursive call, head is now ListNode{val: 4, next: ListNode{val: 5, next: None}} or [4, 5], and newHead = ListNode{val: 5, next: None} or [5], as it is returned from the deepest call. The [5]s in both head and newHead are the SAME listnode. Now, head.next.next = head, so your head should be [4, 5, 4, 5, 4, 5, 4, 5... (its cyclical)], and newhead should be [5, 4, 5, 4, 5, 4...] since the [5] and [4] list nodes are the same between head and newHead. Then call head.next = null so head should be effectively truncated to [4], since head.next is the node after [4] to be removed. newHead is truncated to [5, 4], since anything after the first [4] is removed. From the next level up the recursion call, head is [3, 4] since the listNode [5] was removed from head. head.next.next = head changes head to [3, 4, 3, 4, 3...]. And newHead is [5, 4, 3, 4, 3, 4, 3...]. Then head.next = null truncates head to [3]. Repeat until the list is reversed. Head.next = null effectively stops the linkedList from referencing itself forever.

Alternatively, we can think of the solution as:

1. at each recursive call, we first store the current head to hewHead, this newHead will change from 1 -> .. -> 5 when reached the deepest layer and remains at 5 and gets returned all the way up.
2. head.next.next = head essentially create a loop between 4 and 5, and then head.next = None cut free 4 -> 5 and whats left is 5 - > 4.
3. As the recursive returns up, the head will change from 4 to 3, and then create loop between 3 and 4 with head.next.next = head and then break 3 - > 4 with head.next = None.

code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
	"""
	iterative
	"""
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, cur = None, head
        while cur is not None:
            next_node = cur.next
            cur.next = prev
            prev = cur
            cur = next_node
        return prev
        
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def helper(prev, cur):
            if cur is None:
                return prev
            
            next_node = cur.next
            cur.next = prev
            new_head = helper(cur, next_node)
            return new_head
        
        return helper(None, head)

class NeetSolution:
	"""
	recursive
	"""
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        newHead = head
        if head.next:
            newHead = self.reverseList(head.next)
            head.next.next = head # head will reach 5 and then when it returns, it will be at 4, 3, 2, 1.
        head.next = None
        return newHead # newHead will reach 5 and remains 5 and gets returned all the way up

Complexity

time: $O(n)$
space: $O(1)$ if iterative solution, $O(n)$ if recursive solution.