# #5 [Leetcode 206](https://leetcode.com/problems/reverse-linked-list/) Reverse Linked List

###### tags:`linked list` `easy` `leetcode`

<br>

## Issue

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

### Sample Input & Output


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

Input: head = [1,2]
Output: [2,1]

Input: head = []
Output: []

### Constraints

* The number of nodes in the list is the range [0, 5000].
* -5000 <= Node.val <= 5000

<br>

## Solutions

### Most voted

:::spoiler Javascript ES6 less code solution
Time: O(n)
Space: O(1)

var reverseList = function(head) {
    let [prev, current] = [null, head]
    while(current) {
        [current.next, prev, current] = [prev, current, current.next]
    }
    return prev
}

:::

<br>

:::spoiler Iterative

Time: O(n)
Space: O(1)

var reverseList = function(head) {
    let prev = null
    let curr = head
    let next = null
    
    while(curr!== null){
        // save next
        next = curr.next
        // reverse
        curr.next = prev
        // advance prev and curr
        prev = curr
        curr = next
    }
    return prev;
};

:::

<br>

:::spoiler Recursive

Time: O(n)
Space: O(n)

我看不懂．．．腦容量不足
[教學影片](https://www.youtube.com/watch?v=O0By4Zq0OFc&t=1s)

var reverseList = function(head) {
	// base case
    if (head == null || head.next == null){
        return head;
    }
	// go all the way to the end
    let reversedListHead = reverseList(head.next)
	// add reverse myself
    head.next.next = head;
    head.next = null;
	// go up
    return reversedListHead
};

:::

<br>

### Everyone's

:::spoiler 東
先設定前兩個item, 再去跑迴圈

// Time O(n) | Space O(1)- where n is the amount of node linked to input head
var reverseList = function(head) {
    if(!head) return head;     
    const tail = new ListNode(head.val);
    if(!head.next) return tail;
    
    let prevNode = head;
    let currNode = head.next;
    let nextNode = head.next.next;
    let reversedHead = currNode;
    reversedHead.next = tail;
    
    while(nextNode) {
        prevNode = currNode;
        currNode = nextNode;
        nextNode = nextNode.next;
        reversedHead = currNode;
        reversedHead.next = prevNode;
    }
    return reversedHead;
};

:::

<br>

:::spoiler Becky
先設定好第一個

//time: O(n) | space: O(1)
var reverseList = function(head) {
    if(!head){
        return null;
    }

    if(!head.next){
        return head;
    }

    let prev = head;
    let currentNode  = head.next;
    prev.next = null;

    while(currentNode != null){
        let temp = currentNode;
        currentNode = currentNode.next;
        temp.next = prev; 
        prev = temp;
    }
    return prev;
};

:::

<br>

:::spoiler Hao

/**
 * Time complexity: O(N), Space complexity: O(1)
 */
var reverseList = function(head) {
    let curList = head;
    let newList = null;

    while (curList) {
      const newNode = curList;
      curList = curList.next;
      newNode.next = newList;
      newList = newNode;
    }

    return newList;
};

:::

<br>

:::spoiler YC

/**
 * time: O(n) - where n is the number of nodes in the head
 * space: O(1)
 */
var reverseList = function(head) {
    if(!head) return head;
    let list = null;
    
    while(head){
        const next = head.next;
        head.next = list;
        list = head;
        head = next;
    }
    return list;    
};

:::

<br>

:::spoiler 月薪

// Time O(n) Space(1)
var reverseList = function(head) {
    let result = null; // Record tail til find head
    while(head){
        const record = head.next;
        head.next = result;
        result = head;
        head = record;
    }
    return result;
};

:::

<br>

:::spoiler Raiy

:::

<br>

## Discussion

### destructructuring

[current.next, prev, current] = [prev, current, current.next]