LeetCode #206: Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

To solve this problem in Python 3, we can use a simple iterative approach that iterates through the linked list and reverses its pointers. We can also use a recursive approach that recursively reverses the linked list by changing the next pointer of each node.

Here are the steps to follow for the iterative approach:

1. Initialize two pointers, prev and curr, to None and to the head of the input linked list, respectively.
2. Traverse the linked list by iterating over curr.
3. For each curr node, store its next node in a temporary variable temp.
4. Reverse the pointer of curr to point to prev.
5. Update prev to curr and curr to temp.
6. Repeat steps 3 to 5 until curr becomes None.
7. Return prev as the new head of the reversed linked list.

Here’s the Python 3 code that implements this approach:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        
        return prev

In this code, we first initialize two pointers, prev and curr, to None and to the head of the input linked list, respectively. We then traverse the linked list by iterating over curr. For each curr node, we store its next node in a temporary variable temp.

We then reverse the pointer of curr to point to prev and update prev to curr and curr to temp. We repeat steps 3 to 5 until curr becomes None, indicating that we have reached the end of the linked list.

Finally, we return prev as the new head of the reversed linked list.

The time complexity of the iterative solution is O(n) because we need to iterate over each node of the linked list once. The space complexity is O(1) because we only use a constant amount of extra space to store the pointers prev, curr, and temp.

Here’s the Python 3 code that implements the recursive approach:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        
        return new_head

In this code, we first check if the input linked list is empty or has only one node. If it is, we return the head of the linked list.

Otherwise, we recursively reverse the remaining linked list by calling self.reverseList(head.next) and storing the new head of the reversed linked list in a variable new_head.

We then reverse the pointer of the current node head to point to the previous node, which is now head.next.next. We set the next pointer of the current node to None to break the original link.

Finally, we return new_head as the new head of the reversed linked list.

Time and Space Complexity

The time complexity of the recursive solution is also O(n) because we need to traverse each node of the linked list once. However, the space complexity is O(n) because the recursive call stack can use up to n frames, where n is the number of nodes in the linked list.