LeetCode 206. Reverse Linked List

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

This is such a classic question. I have coded both the recursive and iterative solutions. Linked List can be quite tricky. This reversing the list question is quite good of a demonstration of this. Both of my solutions work, but they are not efficient. I think it will be helpful for others and myself to describe how I come up with the solutions.

The recursive solution is easier to think about. We just need to reverse the list starting after the head, and once the head of the sublist is returned from the recursive call, we iterate that sublist till the last element is reached, and setting that element's next to the head of the original list. The only caveat is to remember setting the head's next to None at the end.

The iterative solution is a bit trickier. If we only maintain 2 points, whenever we assign one of the pointer's next to the other pointer, we lose the reference to the next of the pointer after assignment. This can be solved by maintaining 3 pointers and kept moving forward one step at a time for the 3 pointers. We will keep on moving the points until the middle of the 3 pointers points to the NULL of the last element's next, and simply return the start pointer as the head of the reversed list. My solution is ugly because I need to check for if mid is None inside the while loop. Because when mid already reached the last element's next, which is None, any reference to mid's next will throw exception. Therefore, I am doing that check and essentially breaking out of the while loop.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # Recursive
        # if not head:
        #     return None
        # if head.next:
        #     tmp = self.reverseList(head.next)
        #     cur = tmp
        #     while cur.next:
        #         cur = cur.next
        #     head.next = None
        #     cur.next = head
        #     return tmp
        # else:
        #     return head
        
        # Iterative
        if not head or not head.next:
            return head    
        i = head
        mid = head.next
        j = mid.next
        idx = 0
        while mid:
            mid.next = i
            if idx == 0:
                i.next = None
            i = mid
            mid = j
            if mid:
                j = mid.next
            idx += 1
        return i