# π€ leetcode 206. Reverse Linked List | easy | linked-list | iterative | recursive | javascript

## ποΈ Problems

``````Given the head of a singly linked list, reverse the list,
and return the reversed list.
``````
``````Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
``````

## π€ First attempt

• I don't know why... but I don't like the linked list.
• Among them, especially I don't like reverting the linked list.
• ...
• Let's be more familiar with the linked list further.

## β¨ Idea

• Use the iterative method.
• Use the recursive function.

## β‘οΈ iterative

### π‘ How to revert

``````head -> 1 -> 2 -> ...
|     |
prv   cur

null <- 1 <- 2 <- ...
|    |
prv  cur
``````

### 1. revert: set next of [object Object] ([object Object]) to point [object Object]

``````cur.next = prv;
``````

### 2. backup [object Object] for later usage

``````// backup
const next = cur.next;
// revert
cur.next = prv;
``````

### 3. proceed to the next

``````while (cur) {
...
prv = cur;
cur = next;
}
``````

### π₯πβ‘οΈ My iterative solution

``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
var reverseList = function (head) {
let prv = null;

while (cur) {
const next = cur.next;
cur.next = prv;

prv = cur;
cur = next;
}

return prv;
};
``````

## β»οΈ recursive

• Let's define the recursive function which reverts the linked list in action.
• revert all beneath the given node.
``````  const reverse = node => {
...
return XXX
};
``````

### The result

• is just calling the recursive function `reverse(head)` with the head node.
``````return reverse(head);
``````

### β»οΈ inside the recursive function

#### 0. problem

``````head -> 1 -> 2 -> 3 -> 4 -> 5 -> null

null <- 1 <- 2 <- 3 <- 4 <- 5 <- head
``````

#### 1. basecase

• If the node is null or the only node (next is null), no need to revert.
• Just return the node.
``````if (!node || node.next === null) return node;
``````

#### 2. π‘ revert except for the head node

``````const last = reverse(node.next);
``````
• `last` is the new head of the reverted linked list.
• should be returned as the head of the reverted linked list.
``````// proceed to the end
reverse(1,2,3,4,5)

|
1 => reverse(2,3,4,5)
|
1 => 2 => reverse(3,4,5)
|
1 => 2 => 3 => reverse(4,5)
|
1 => 2 => 3 => 4 => reverse(5)

1 => 2 => 3 => 4 => 5
|
last
``````

#### 3. π‘ after returning from the end

• let `node` point back to `node`
• set `node` null
• only the head node remains `null`.
• the beneath node was set to be `null`, but later changed to point the previous node after returning `revert()` function.
``````head
|
1 => 2 => 3 => 4 => 5

// revert
node -> // node.next
<- // node.next.next

node.next.next = node;
node = null;

1 <= 2 <= 3 <= 4 <= 5
|                   |
null               last
``````

#### β¬οΈβ»οΈ 4. put together

``````const reverse = (node) => {
if (!node || node.next === null) return node;

const last = reverse(node.next);

node.next.next = node;
node.next = null;

return last;
};
``````

#### π 5. final result

``````null <- 1 <- 2 <- 3 <- 4 <- 5
``````

### π₯πβ¬οΈβ»οΈ My recursive solution

``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
var reverseList = function (head) {
const reverse = (node) => {
if (!node || node.next === null) return node;

const last = reverse(node.next);

node.next.next = node;
node.next = null;

return last;
};