[LeetCode 206] [Easy] Reverse a Linked List

Question

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

Input: head = [1,2,3,4,5]

1 -> 2 -> 3 -> 4 -> 5 -> None

Output: [5,4,3,2,1]

5 -> 4 -> 3 -> 2 -> 1 -> None

Solution

Using three variables, currentNode, which tracks the current node that you would like to readjust its pointer, nextNode, to hold the original currentNode’s next pointer reference, and the prevNode to track the currentNode once all adjustments has been made.

We will stop the loop once all readjustments for each node in the original linked list has been completed.

1. First we will capture the current node’s neighbouring node in nextNode, this will help has hold the temporary value of the original next pointer reference of the current node.
2. Next we will update the currentNode’s next pointer to the previously modified node where the readjustment has been completed. (i.e. where its starts with None when its first initialised)
3. Update the prevNode to the current node once its pointer has been modified to the reverse order
4. Reassign the currentNode to the original next node, that is stored in nextNode

Code

# time: o(n)
# space: o(1)
def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """ 

        currentNode = head
        nextNode = None
        prevNode = None
        while currentNode is not None:
            # capture the current node's neighbouring node
            nextNode = currentNode.next
            # update the current node's next pointer to the previous node
            currentNode.next = prevNode
            # update the PrevNode now to the currentNode
            prevNode = currentNode
            # update the current node to the original next node
            currentNode = nextNode
        
        return prevNode