力扣JS 19. 删除链表的倒数第 N 个结点 面试题 02.07. 链表相交

菜鸡刷算法的一天，每天分享两题算法，大家有这个想法的，可以给我个关注，然后一起坚持每天的算法之旅。希望我们共同进步，一起加油。 LC 19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

 

解题思路：设置快慢指针，让快指针先走 n ，然后快慢指针再一起往后走，直到快指针走到最后一个节点的时候 ，慢指针的下一个节点就是要删除的节点

 

代码：

var removeNthFromEnd = function(head, n) {
    let fast = head, slow = head; //快慢指针
    while(n--) { //让快指针指向 n 个节点后的节点，快慢指针中间就间隔 n
        fast = fast.next;
    }
    if(!fast) { //如果 fast 为null 的话，说明 n 和链表长度一样。删除的节点就为头结点
        return head.next
    }
    while(fast.next != null) { //如果快指针没有走到最后一位，那么快慢指针就一起往后走。
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next; //当快指针指向最后一个节点的时候，慢指针的下一个节点刚好就是要删除的节点
    return head;
};

 

LC 面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

 

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

 

解题思路：将其中一个表遍历放进哈希表中，然后遍历另一个表跟哈希表内的值比对，一样的就返回这个值，没有一样的就返回 null

代码：

var getIntersectionNode = function(headA, headB) {
    const map = new Set(); //创建一个哈希表
    let temp = headA;
    while(temp !== null) { //遍历表A,将A放进去哈希表中
        map.add(temp);
        temp = temp.next;
    }
    temp = headB;
    while(temp !== null) {  //遍历表B, 查看哈希表中有没有一样的值，有就返回这个值，没有就返回 null
        if(map.has(temp)) {
            return temp;
        }
        temp = temp.next;
    }
    return null;
};