Day04 | 24.两两交换链表中的节点、19.删除链表的倒数第N个节点、02.07.链表相交、142.环形链表II

Leetcode 24.两两交换链表中的节点

题目：24.两两交换链表中的节点 讲解：https://www.bilibili.com/video/BV1YT411g7br/

初始思路

一开始没什么思路，直接看的视频讲解，自己画了图。

代码

var swapPairs = function (head) {
    let dummyHead = new ListNode(0, head)
    let temp = dummyHead
    // temp指向需要交换的两个节点的前一个节点
    while (temp.next && temp.next.next) {
        let current = temp.next.next
        let previous = temp.next
        previous.next = current.next
        current.next = previous
        temp.next = current
        // 获得下一次交换两个节点的前一个节点
        temp = previous
    }
    return dummyHead.next
};

感想

1. 方法很巧妙。
2. 同样使用了虚拟头结点，这样就不用额外处理头结点了
3. 如果不加第四步，让temp继续往后移动的话会死循环。
4. 

Leetcode 19.删除链表的倒数第N个节点

题目：19.删除链表的倒数第N个节点 讲解：https://www.bilibili.com/video/BV1vW4y1U7Gf/

初始思路

暴力解法：第一遍遍历获得链表的长度，第二遍遍历的时候找到需要删除的节点，因为传入的N和下标的和为链表的长度。需要两遍遍历。

代码

var removeNthFromEnd = function (head, n) {
    let dummyHead = new ListNode(0, head)
    let slow = fast = dummyHead
    while (n--) {
        // fast指针先移动n步
        fast = fast.next
    }
    while (fast.next !== null) {
        fast = fast.next
        slow = slow.next
    }
    // 此时slow指向需要删除的节点的上一个节点
    slow.next = slow.next.next
    return dummyHead.next
};

感想

1. 暴力解法也可以使用，但是如果特别指明只能使用一次遍历的话就只能使用双指针解法。
2. 双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向下一个节点就可以了。

Leetcode 面试题 02.07. 链表相交

题目：面试题 02.07. 链表相交

初始思路

没接触过这样的题目，看了题解之后发现还是挺简单的。

代码

var getListLen = function (head) {
    // 计算链表的长度
    let length = 0
    let current = head
    while (current) {
        length++
        current = current.next
    }
    return length
}
var getIntersectionNode = function (headA, headB) {
    let currentA = headA, currentB = headB
    let lengthA = getListLen(headA)
    let lengthB = getListLen(headB)
    if (lengthA < lengthB) {
        // 把短的链表放到B里，方便对齐
        // 下面交换变量注意加 “分号” ，两个数组交换变量在同一个作用域下时
        // 如果不加分号，下面两条代码等同于一条代码: [curA, curB] = [lenB, lenA]
        [currentA, currentB] = [currentB, currentA];
        [lengthA, lengthB] = [lengthB, lengthA];
    }
    // 移动多出来的长度，末尾对齐
    let delta = lengthA - lengthB
    while (delta-- > 0) {
        currentA = currentA.next
    }
    while (currentA && currentA !== currentB) {
        // 当两个指针相同的时候就遇到了交叉点
        currentA = currentA.next
        currentB = currentB.next
    }
    return currentA
};

感想

1. 如果链表相交，末尾一定是相交的片段。长度是固定的，所以让两个链表尾端对齐就可以找到相交点。
2. 思路很简单，但是之前没接触过，所以没想出来。

Leetcode 142.环形链表II

题目：142.环形链表II 讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html

初始思路

相比较141题，这题不仅要判断是否有环，还要找到入环的地方。
使用快慢指针就可以判断是否有环，因为有环的话两者一定会相遇。

代码

var detectCycle = function (head) {
    let slow = head
    let fast = head
    while (true) {
        if (fast == null || fast.next == null) return null
        slow = slow.next
        fast = fast.next.next
        // 此时相遇点在slow节点
        if (fast === slow) break
    }
    // 让fast节点回到头结点开始同时移动
    fast = head
    while (fast !== slow) {
        // 此时每个指针只走一步，相遇的地方就是环的入口
        fast = fast.next
        slow = slow.next
    }
    return fast
};

感想

1. 讲解的非常到位，甚至还有推导。
2. 使用快慢指针，快指针每次走两步，慢指针每次走一步，如果链表有环，那么两者一定会在环内相遇。slow记住此时的相遇点，让fast回到头结点开始，两者此时每次都走一步，当两者再次相遇的时候，就是环的入口。
3. 代码写起来不复杂， 但是想法很难想到，需要背下来的结论。