01.链表题

1. 反转链表的写法
2. 移动节点位置为m的写法：1 ≤ m ≤ n ≤ 链表长度

// head有可能被删掉，所以需要创建dummyNode节点
let dummyNode = new ListNode();
dummyNode.next = head;

let pre = dummyNode;
let cur = head

return dummyNode.next

新链表的固定写法

var dummyNode = new ListNode();
var cur = dummyNode;
cur.next = ...; // 保存操作
cur = cur.next; // 移动指针

赋值规律记忆：

// 对于链表有两个操作：更新指针 以及 断链/重联链
// 1. 更新指针：写法（等号前一定不带.next）
// cur = cur.next; pre = pre.next ; cur = cur.next.next

// 2.改变链表结构
// cur.next 含义是 cur的下一个节点是......
// (起始链头).next = 终止链尾
// cur.next = .... 此时只是链的重新连接，后续还需要指针更新

83.删除排序链表中的重复元素 (opens new window)

题解：

• 链表基础题
• 注意if条件中是否用到cur.next，需要放到while

伪代码：

// 先将head保存到cur中
let cur = head; 
while(cur !==null && cur.next !==null){
    if(条件){
        跳转节点
    }else{
        更新cur
    }
}
return head;

点击查看

参考代码:

var deleteDuplicates = function(head) {
    let cur = head;
    while(cur !== null && cur.next !== null){
        if(cur.val === cur.next.val){
            cur.next = cur.next.next
        }else{
            cur = cur.next;
        }
    }
    return head
};

92.反转链表 II (opens new window)

题解：

• 反转链表，需要先将cur.next提前保存下来，最后需要赋值给cur

• 需要额外两个变量保存住链表的位置：before、after

伪代码：

//1.判断head是否为空节点
//2.设置虚拟节点，pre -> dummyNode,cur -> head
const dummyNode = new ListNode();
dummyNode.next = head;
let pre,cur = ...;

//3.找before、after的位置
for(移动m-1步){更新cur、pre}
结束后，保存当前的cur和pre的指针所在的位置 --> before、after

//4.反转
for(移动n-m+1步){
    反转固定写法[核心：临时保存cur.next]
}
//5.处理before和after
//【这需要比较深入的分析，这里可以直接背下来就好了】
before.next = pre;
after.next = cur;

return dummyNode.next;

点击查看

参考代码：

var reverseBetween = function(head, m, n) {
    if(!head){
        return head;
    }
    const dummyNode = new ListNode();
    dummyNode.next = head;
    let pre = dummyNode,cur = head;
    console.log(cur.val)
    for(let i=0;i<m-1;i++){
        pre = pre.next;
        cur = cur.next;
    }
    console.log(cur.val);
    let before = pre, after = cur;
    for(let i=0;i<n - m + 1;i++){
        bak = cur.next;
        cur.next = pre;
        pre = cur;
        cur = bak;
    }
    before.next = pre;
    after.next = cur;
    return dummyNode.next;
};

19.删除链表的倒数第N个节点 (opens new window)

题解：

• 使用双指针，让两者相隔n步。

  分析：若需要删除倒数第2个节点，则需要让指针移动到倒数第3个节点。

• n1 和 n2 必须指向dummyNode【若只有1个节点，需要删除头结点，返回Null很困难】

伪代码：

dummyNode = new ListNode();
dummyNode.next = head;
let n1,n2 = dummyNode;
//1. 让两者相隔n+1步
for(循环n+1步){n1 = n1.next}
//2. 让n2移动到null
while(n2 !== null){
    更新n1和n2
}
//3. 删除节点
n1.next = n1.next.next;
//4. return dummyNode.next

点击查看

参考代码:

var removeNthFromEnd = function(head, n) {
    var dummy = new ListNode();
    dummy.next = head;
    var p1 = dummy;
    var p2 = dummy;
    // 让p2指针先走n+1步，让p2走到null，此时p1走到3
    for(let i=0; i<=n;i++){
        p2 = p2.next;
    };

    while(p2 !== null){
        p1 = p1.next;
        p2 = p2.next
    }
    p1.next = p1.next.next;
    return dummy.next
};

21.合并两个有序链表 (opens new window)

题解：

• 首先该两链表是升序链表
• 指定两个指针：l1和l2分别读取两个链表
• 知识点：新链表的创建

伪代码：

let p = new ListNode();
// 将头结点保存一下
let dummyNode = p;

while(l1!==null && l2!==null){
    if(l1.val<l2.val){
       	将l1的节点压入新的链表中
        l1 = l1.next
    }else{
        否则，操作同上
    }
    新链表指针+1;
}

// 将剩余部分添加到新链表
if(l1 !==null){
    l1压入新链表
}else{
    l2压入新链表
}
// return dummyNode.next

点击查看

参考代码:

var mergeTwoLists = function(l1, l2) {
    // 使用一个新的指针：即工作区，类似于之前合并数组区间
    // dummy 作用：保存一下头结点
    let cur = new ListNode();
    let dummy = cur;

    while (l1 !== null && l2 !== null) {
        // && 并集，必须考虑并集外的情况
        if(l1.val<=l2.val){
            cur.next = l1;
            l1 = l1.next;
        }else{
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    // 并集外的情况
    if(l1 !==null){
        cur.next = l1;
    }else{
        cur.next =l2;
    }
    return dummy.next;
};

141.环形链表 (opens new window)

题解：

• 知识点：快慢指针
• while循环条件：fast !== null && fast.next !== null
  • slow = slow.next'
  • fast = fast.next.next

经典代码：

var hasCycle = function(head) {
    if(head === null){
        return false;
    }
    // 快慢指针
    let slow = head;
    let fast = head;
    while(fast !== null && fast.next !==null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast){
            // 存在环
            return true;
        }
    }
    return false;
};

142.环形链表 II (opens new window)

题解：

• 核心知识点：快慢指针
• 快慢指针的入口节点：在fast和slow相遇的时候，将fast指针再次移到头部，直至两者再此相遇。

经典代码：

var detectCycle = function(head) {
    var fast = head;
    var slow = head;
    while(fast !==null && fast.next !==null){
        fast = fast.next.next;
        slow = slow.next;
        if(slow == fast){
            break;
        }
    }
    // 循环外部存在两种情况：
    //1. slow或者fast相遇 
    //2. 此时fast指针是 null 或者 fast.next是 null
    if(fast == null || fast.next ==null){
        return null;
    }
    fast = head;
    while(fast!==slow){
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
};

876.链表的中间结点 (opens new window)

题解：

• 知识点：利用快慢指针去寻找链表的中间结点。

  

经典代码：

var middleNode = function(head) {
    let slow = head;
    let fast = head;
    while(fast !==null && fast.next !== null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

206.反转链表 (opens new window)

经典代码：

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

24.两两交换链表中的节点 (opens new window)

题解：

• 需要准备一个指针p指向dummyNode，p.next与p.next.next分别指向第1个节点和第2个节点；结束时，将p指针移动到现原先p.next的位置【但在操作过程中对原链表的结构发生了变化，故需要先将p.next的值先保存下来】

• 因为步骤太多，所以简化记忆

  1. 第一步将p.next和p.next.next保存下来【1，2的位置】
  2. 先链接l2节点
  3. l2指向l1
  4. l1指向l2的后一节点
  5. 经过上述步骤已经排序结束，故将p指针移动至l1的位置。
  

  链表的调整顺序原则：[下上中]【如图说明】

  1. 下：p指向4后【即，无法再通过p获取3和4，所以必须提前保存两者的位置】
  2. 中：4指向3的前提是上：3必须先指向5。【即，中间的指向必须是最后确定的】

经典代码:

var swapPairs = function(head) {
    //1. 创建dummyNode节点
    let dummyNode = new ListNode();
    dummyNode.next = head;
    //2. 将工作指针移动到dummyNode
    let p = dummyNode;
    while( p.next !==null && p.next.next !==null){
        let l1 = p.next;
        let l2 = p.next.next;
        p.next = l2;
        l1.next = l2.next;
        l2.next = l1;
        p = l1;
    }
    return dummyNode.next;
};

2. 两数相加 (opens new window)

题解：

• 使用链表来存储数字，必须是个数在尾结点。
• 通过l1和l2去取出同位数的数字
• 使用sum去缓存相同位数的结果
  • 将sum中的个位数保存到新链表中
  • 将sum中的十位数保存到carry变量中

伪代码：

// 创建新链表
let dummyNode = new ListNode();
let cur = dummyNode;
let carry = 0;
while(l1和l2都不为空，两者是或的关系){
    let sum = 0;
    if(l1 !== null){1.更新sum 2.移动l1指针}
    if(l2 !== null){1.更新sum 2.移动l2指针}
    sum+=carry 
   	// 提取sum的两个部分，一部分更新为carry，一部分保存为cur中
}
if(假如最后carry中还有指，则放置开头){
    cur.next = new ListNode(carry)
}
return dummyNode.next

445.两数相加 II (opens new window)

题解：

• 在第2题的基础上，可以很好的理解链表为什么要倒存数。
• 使用stack倒着保存链表值。

伪代码：

// 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
// 输出：7 -> 8 -> 0 -> 7

// 第1步：构造stack 
// stack1 = [7,2,4,3] ; stack2 = [5,6,4] 

// 第2步：同第2题的算法
while(stack1.length !== 0 || stack2.length !== 0){}

点击查看

参考代码：

var addTwoNumbers = function(l1, l2) {
    var stack1 = [];
    var stack2 = [];
    while (l1 !== null) {
        stack1.push(l1.val);
        l1 = l1.next;
    }
    while (l2 !== null) {
        stack2.push(l2.val);
        l2 = l2.next;
    }

    var carry = 0;
    var curr = null;
    while (stack1.length !== 0 || stack2.length !== 0) {
        let sum = 0;
        if (stack1.length !== 0) {
            sum += stack1.pop();
        }
        if (stack2.length !== 0) {
            sum += stack2.pop();
        }
        sum += carry;

        // 取sum, 个位和十位
        carry = Math.floor(sum / 10);
        const node = new ListNode(sum % 10);

        //  需要将刚得到的node，添加到链表的头部
        node.next = curr;
        curr = node;       
    }

    if(carry !== 0){
        var node = new ListNode(carry)
        node.next = curr;   
        curr = node;
    }
    return curr;
};

160.相交链表 (opens new window)

题解：

• 因为A和B链表的长度不同，说明：当A的链表指针走到头，就将A链表的指针移到B链表的头部。

伪代码：

// p1 和 p2 指向头部
while(p1和p2不停地在比较){
    if(p1有无到头部){
        到了，就将其移动到对面的B链表头部
    }else{
        若没有到，就正常跌倒更新
    }
}
直接return l1 or l2

此时，考虑到了 l1 和 l2 皆为null的情况，

点击查看

参考代码：

var getIntersectionNode = function(headA, headB) {
    let l1 = headA;
    let l2 = headB;
    while(l1 !== l2){
        if(l1 !== null){
            l1 = l1.next;
        }else{
            l1 = headB;
        }
        if(l2 !== null){
            l2 = l2.next;
        }else{
            l2 = headA;
        }
    }   
    return l1;
};