链表

[AILINGANGEL]

链表反转

• 递归

var reverseList = function(head) {
    if (head === null || head.next === null) {
        return head;
    }
    let newHead = reverseList(head.next);
    head.next.next = head;// 让已经反转的链表的最后一个节点指向当前节点
    head.next = null;//让当前这个点的下一个节点指向null,保证让最开始的头结点变成尾节点
    return newHead;
};

• 迭代
  核心思想：用pre记录上一个节点，初始为null;用cur记录当前节点；每次迭代保存cur的下一个节点next, 因为要修改cur的next指向为pre;然后将当前节点cur变成上一个节点pre, 让next变成cur当前节点，这样迭代进行。知道cur指向的节点为空。

var reverseList = function(head) {
    let pre = null;
    let cur = head;
    while (cur) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}