Problem statement

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

Solution

The idea is to keep 2 pointers for current and next node and then iterate through nodes and reconnect nodes. The best way to understand this solution is to take some small list, for example 1 -> 2 -> 3 -> 4 -> None and see what is going on on the each step.

  1. In the beginning curr = None, nxt = 1.
  2. On the first step we have: tmp = 2, nxt.next = None, curr = 1, nxt = 2. So what we have is the following: None <- 1 2 -> 3 -> 4 -> None. That is we cut one link between 1 and 2 and create new link 1 -> None.
  3. On the next step we have None <- 1 <- 2 3 -> 4 -> None and so on.

Try to draw it on the paper, step by step, it is the best way to feel it.

Complexity

Time complexity is O(n), space is O(1).

Code

class Solution:
    def reverseList(self, head):
        curr = None
        nxt = head
        while nxt:
            tmp = nxt.next
            nxt.next = curr
            curr = nxt
            nxt = tmp
            
        return curr