代码随想录Day4-Leetcode24-两两交换链表中的节点， 19.删除链表的倒数第N个节点， 142.环形链表II()-其他

发表于： 3月 19, 2023 3月 19, 2023
分类：其他
标签：其他

代码随想录Day4-Leetcode24-两两交换链表中的节点， 19.删除链表的倒数第N个节点， 142.环形链表II()

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

题目链接:https://leetcode.cn/problems/swap-nodes-in-pairs
比较简单的链表题, 注意使用虚拟头结点和注意变量就没问题


/**
 * 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}
 */
var swapPairs = function(head) {
    if(head == null||head.next == null){
        return head
    }
    let vHead = new ListNode(-1,head)
    let pre = vHead , p1 = head, p2 = head.next
    while(true){
        let tmp = p2.next
        p2.next = p1
        p1.next = tmp
        pre.next = p2
        tmp = p1
        p1 = p2
        p2 = tmp
        for(let i = 0 ;i<2;i++){
            if(p2.next!=null){
                p2 =p2.next
                p1 = p1.next
                pre = pre.next
            }else{
                return vHead.next
            }
        }

    }
};

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

题目链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list
这题写过,所以还挺快的,双指针秒A(终于有一天我也能有秒A的题了,虽然是简单题,还是做过的)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {

    let vHead = new ListNode(-1,head)
    let slow = vHead, fast = vHead
    for(let i =0; i<n;i++){
        fast = fast.next
    }
    while(fast.next!=null){
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return vHead.next
};

面试题 02.07. 链表相交

这题偷懒用set了,好方便
知道可以用快慢指针, 但数学推导有点麻烦

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
 //同样可以快慢指针, 但需要数学推导
 //如果可用map或set
var getIntersectionNode = function(headA, headB) {
    let set = new Set()
    
    let pa = headA
    let pb = headB
    while(pa!=null){
        set.add(pa)
        pa = pa.next
    }
    while(pb!=null){
        if(set.has(pb)){
            return pb
        }
        pb = pb.next
    }
    return null

};

142.环形链表II

这题看了题解, 确实不太好想出来
需要一点数学上的灵感, 或者稳稳的慢慢推导

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
 //思路:快慢指针,最后会相遇,但我忘记算法了
 //map?
var detectCycle = function(head) {
    if(head == null||head.next == null){
        return null
    }
    let fast = head, slow = head
    while(true){
        for(let i = 0; i<2; i++){
            if(fast.next!=null){
                fast = fast.next
            }else{
                return null
            }
        }
        slow = slow.next
        if(slow === fast){
            //相遇//很多时候不能看语句的数量来评价算法复杂度, 就这句能写出来,不简单
            fast = head
            while(slow!==fast){
                fast = fast.next
                slow = slow.next
            }
            return slow
        }
        //a b
        //s 2s = s+nb
        //s= nb
        //到交叉点的路程a+nb
    }
};

————————