[数据结构与算法]leetcode-链表

206-反转链表

代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// solution1 迭代法
 var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while(curr !== null){
        // 先把 current 的下一个 给存起来 不然指针断开，current不能往下遍历
        const next = curr.next;
        // 反转指针 curr的下一个指向 prev
        curr.next = prev;
        // 反转完之后 往下顺序移动 prev 和 curr
        prev = curr;
        // 这里就说明了为什么curr.next 要先存起来  因为curr 反转完之后要往下走 如果不存 那么curr.next 就是 prev了
        curr = next;

    }
    // 最后我们要返回的是表头 也就是prev在的位置
    return prev;


};

```javascript
// solution2 递归法
var reverseList1 = function(head){
    // 递归终止条件 head ==null 传入的head是null 的话 返回 head  
    // head.next == null这是归的过程中赋值的 此时我们已经反转了head 和body 不管 body怎么样 head位置是对的 所以返回 head
    if(head ==null || head.next == null){
            return head
        }
        // 开始归
        const p = reverseList1(head.next);
        // 递归核心代码         
        head.next.next = head;
        head.next = null;
        // return p 最后其实也是return head 因为要从头走一遍
        return p;
   
    
}

这个视频思路很清楚：https://leetcode-cn.com/problems/reverse-linked-list/solution/shi-pin-jiang-jie-die-dai-he-di-gui-hen-hswxy/

笔记我记在notablity里了 P15左右