206. 反转链表.md

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

solution: 1.迭代1️⃣

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (!head) return head
    let temp = head
    let linkList = []
    linkList.push(Object.assign({}, head))
    linkList[0].next = null
    while(temp.next) {
        temp = temp.next
        linkList.push(Object.assign({}, temp))
        linkList[linkList.length - 1].next = linkList[linkList.length - 2]
    }
    return linkList[linkList.length - 1]
};

2.迭代2️⃣

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (!head || !head.next) return head
    let newLink = {
        val: head.val,
        next: null
    }
    while(head.next) {
        head = head.next
        const nextLink = Object.assign({}, newLink)
        newLink = {
            val: head.val,
            next: nextLink
        }
    }
    return newLink
};

3.递归

• 递归的思路有点复杂，假设链表是[1, 2, 3, 4, 5]从最底层最后一个reverseList(5)来看

1. 返回了5这个节点
2. reverseList(4)中
3. p为5
4. head.next.next = head 相当于 5 -> 4
5. 现在节点情况为 4 -> 5 -> 4
6. head.next = null,切断4 -> 5 这一条，现在只有 5 -> 4
7. 返回（return）p为5，5 -> 4
8. 返回上一层reverseList(3)
9. 处理完后返回的是4 -> 3
10. 依次向上

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (!head || !head.next) return head
    const p = reverseList(head.next)
    head.next.next = head
    head.next = null
    return p
};