Reverse a Linked List

Problem

Reverse a singly linked list.

For example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Thought Process

• To reverse a LinkedList, we need to reverse one node at a time. We will start with a variable currentwhich will initially point to the head of the LinkedList and a variable previous which will point to the previous node that we have processed; initially previous will point to null.

• In a stepwise manner, we will reverse the current node by pointing it to the previous before moving on to the next node. Also, we will update the previous to always point to the previous node that we have processed.

Solution

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        current, previous, nextP = head, None, None
        
        while current:
            nextP = current.next
            current.next = previous
            previous = current
            current = nextP
            
        return previous
        
#Time: O(n)
#Space: O(1)