跟着代码随想录练算法——链表（js）

跟着代码随想录练算法——链表（js） [203. 移除链表元素](https://leetcode.cn/problems/remove-linked-list-elements/)[206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)[24. 两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/)[19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)[面试题 02.07. 链表相交](https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/)[142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/)

203. 移除链表元素

考虑到可能要移除链表头结点，可以直接在链表上 *** 作，但是这里需要作为一种情况单独考虑；也可以在链表头结点之前再添加一个节点，这样移除头结点也可以有像移除其他节点一样的 *** 作，不需要特判

直接在链表上 *** 作

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

添加一个新的结点

function ListNode(val, next) {
     this.val = (val===undefined ? 0 : val)
     this.next = (next===undefined ? null : next)
 }
var removeElements = function(head, val) {
    let node = new ListNode(-1, head)
    let cur = node
    while(node.next){
        if(node.next.val === val){
            node.next = node.next.next
        }else node = node.next
        
    }
    return cur.next
};

206. 反转链表

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

24. 两两交换链表中的节点 new 一个虚拟的头结点 node 指向 head，p1，p2 为当前需要交换的两个节点，next 作为除去当前交换节点的第一个节点while 循环遍历链表，循环结束的条件是 p1 为空或者 p2 为空p1 为空对应偶数个节点的链表 *** 作结束，p2 为空对应奇数个节点的链表 *** 作结束while循环体： 先将后续链表节点用next 存下来pre 的下一个指向 p2p2 的下一个指向 p1p1 的下一个指向 next到这里两个节点的交换就完成了 ，从 pre -> p1 -> p2 -> next 到 pre -> p2 -> p1 -> next，接下来就是后移节点继续定位到下一对需要交换的节点了pre 指向 p1p1 指向 next，若发现p1 为空，则证明偶数个节点的链表已经交换结束，break 出去p2 指向next 的next，若发现p1 为空，则证明奇数个节点的链表已经交换结束 最终返回 node.next

function ListNode(val, next) {
  this.val = (val===undefined ? 0 : val)
  this.next = (next===undefined ? null : next)
}
var swapPairs = function(head) {
    if(!head || !head.next) return head
    let node = new ListNode(-1,head)
    let pre = node
    let p1 = node.next
    let p2 = p1.next
    let next = null
    while(p2){
        next = p2.next
        pre.next = p2
        p2.next = p1
        p1.next = next
        pre = p1
        p1 = next
        if(p1 === null) break 
        p2 = next.next
    }
    return node.next
};

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

这题可以先找到倒数第 n-1个节点，然后直接删掉它的下一个节点。因为有可能要删掉头结点，所以给这个链表添加了一个虚拟头结点 node。如何遍历一遍找到倒数第 n-1 个节点呢？使用双指针 p1,p2,p1初始化指向 node,p2初始化指向 node.next,p2往后走一步，n 就 --，当 n <= 0的时候 ，p1也往后移动，当 p2 指向null的时候，p1指向倒数第n-1个节点。

function ListNode(val, next) {
  this.val = (val===undefined ? 0 : val)
  this.next = (next===undefined ? null : next)
}
var removeNthFromEnd = function(head, n) {
    if(!head) return head
    let node = new ListNode(-1,head)
    let p1 = node
    let p2 = node.next  // 快指针
    while(p2){
        p2 = p2.next
        if(n <= 0) p1 = p1.next
        n --
    }
    console.log(p1.val)
    // 结束循环之后 p1 指向需要删除节点的前一个
    p1.next = p1.next.next
    return node.next
};

面试题 02.07. 链表相交

两个链表长度不一样如何确定交点起始位置呢？可以先让p1把headA走一遍，p2把headB走一遍，当p1走完时，再去走p2,当p2走完时再去走p1,第二趟如果两者相等，则表白此时出去公共部分的起始位置

flagA,flagB 表示两个指针是否已经换过链表遍历了循环的结束条件为 p1,p1都不为空，如果有一个为空都表示没有公共部分当两个指针都已经换过链表遍历并且当前相等，则返回当前节点当指针走到链表末尾，判断flagA,flagB是否为0，为0表示还没有换过链表，那就换另外一个链表遍历，不为0表示之前已经更换过了，直接跳出循环

var getIntersectionNode = function(headA, headB) {
    let flagA = 0
    let flagB = 0
    let p1 = headA
    let p2 = headB
    while(p1&&p2){
        if(flagA && flagB && p1 === p2){
            return p1
        }
        if(p1.next){
            p1 = p1.next
        } 
        else{
            if(flagA == 0){
                flagA = 1
                p1 = headB
            }else break
        }
        if(p2.next){
            p2 = p2.next
        }else{
            if(flagB == 0){
                p2 = headA
                flagB = 1
            }else break
        }
    }
    return null
};

142. 环形链表 II

第二遍做这个题了，还是没有根据快慢指针的路程得出那个需要的等式，又看了一遍题解的推导过程，希望我第三遍遇到这个题我能自己写出来吧，呜呜呜。

var detectCycle = function(head) {
    if(!head || !head.next) return null
    let slow = head
    let fast = head
    let p
    while(slow && fast){
        //slow fast 只有有一个走到空 就说明没有环
        if(slow.next) slow = slow.next
        else return null
        if(fast.next && fast.next.next) fast = fast.next.next
        else return null
        // 第一次相遇
        if(slow === fast){
            p = head
            break
        }
    }
    while(p && slow){
        if(p === slow) return p
        if(p && p.next) p = p.next
        if(slow.next) slow = slow.next
    }
    return null
};