206. Reverse Linked List

Today, I solved the Reverse Linked List. 

Description:

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

In this problem, we reverse the order of single linked list.

My idea was that changing the pointer to make reverse order. So, I thought I should change like this "1->2" as a "2->1" repeatedly. In the description of the question, we can see "A linked list can be reversed either iteratively or recursively." 

I'm not sure about this kind of question with python. Here is solution for this problem. 

 

Solution1(Iteractive Method):

Iteractive method

In iteractive method, we use the three variable: prev, curr and head. First, we declare prev as None(empty). 

 

We use loop to run this code until 'head' points to None (the next of 5 in this case!) Below the code, I made the description of method as comments. 

1. The first head is '1', so we make curr points to head
2. head moves to next, so now 2 is head.
3. curr.next points to prev, so it is None
4. Now prev points to '1'!

This method, we move our head and prev. curr is the temporary variable to change the pointer of head and prev!

 

Now, we are gonna look another method using recursion.

Solution2(Recursive Method):

Recursive Method

For recursion function, I put one more parameter prev in reverseList(). Same with Iteractive method, we are gonna end up the recursion when head points to None. That's why I put "if not head return prev." Algorithms is also same with iteractive method. 

1. curr points to the head next (point 2 in the first case)
2. The next node of head is gonna be prev (point None in the first case)
3. Finally, we pass curr, head recursively (curr = 2, head = 1 in ths first case)
4. Now, new head would be curr, and new prev would be head (new head =2, prev = 1 after the first case)