算法之链表相交 - 翁先森的博客

面试题 02.07.链表相交

解题思路：

1.假设两个链表相交于A，由于两个链表都是单向链表，所以A后面的所有节点都是两个链表的公共部分。现在要找它们第一个公共节点，如果可以从后往前找，则找到两个链表第一个不相同的节点，其后的节点即为所求。但链表的特点导致其更适合从前向后遍历，如果要从后往前一个个比较，则每次都要从头扫描找到合适位置的节点再进行比较（最多扫描N趟，平均扫描N/2趟，其中N为链表长度），这样时间复杂度会很高，是平方级的时间复杂度。要想从后往前一个个比较，又不需要每次从头扫描，可以考虑把两个链表的节点分别依次放入两个栈中，这样栈顶的元素便是其最后的节点，逐个出栈并进行比较，即可得到结果。不过这样做需要引入两个栈，而栈的空间复杂度为线性级。这相当于用空间换时间。最后，再仔细分析一下为什么不能从头开始扫描两个链表并用于比较，这是因为两个链表的长度不一样，如果两个链表的长度一样，则由于其公共节点个数一样，所以不相同节点数目也一样，这样完全可以从头扫描并进行比较。但实际给定的两个链表并不一定长度相同，这时可以先让较长的链表走上k(k为长链表与短链表的差值)步，在依次比较两个链表的节点，这样便可以不使用复杂的数据结构，从而保证常量级的空间复杂度。同时，由于用这种方法只需扫描两个链表最多两趟，因此时间复杂度为线性级。

1
/**
2
 * Definition for singly-linked list.
3
 * function ListNode(val) {
4
 *     this.val = val;
5
 *     this.next = null;
6
 * }
7
 */
8

9
/**
10
 * @param {ListNode} headA
11
 * @param {ListNode} headB
12
 * @return {ListNode}
13
 */
14
var getIntersectionNode = function (headA, headB) {
15
    let headALen = 0;
16
    let p = headA;
17
    while (p) {
18
        headALen++;
19
        p = p.next;
20
    }
21
    let headBLen = 0;
22
    let q = headB;
23
    while (q) {
24
        headBLen++;
25
        q = q.next;
26
    }
27
    if (headALen < headBLen) {
28
        p = headA;
29
        headA = headB;
30
        headB = p;
31
        [headALen, headBLen] = [headBLen, headALen];
32
    }
33
    while (headALen - headBLen) {
34
        headA = headA.next;
35
        headALen--;
36
    }
37
    while (headA && headB) {
38
        if (headA === headB) {
39
            return headA;
40
        }
41
        headA = headA.next;
42
        headB = headB.next;
43
    }
44
    return null;
45
};

2.两个指针最多走过headA链表长度 + headB链表长度的距离

如果相交，会提前相遇在相交节点。此时返回相交节点。如果不相交，则各自走过headA链表长度 + headB链表长度的距离，指向null。此时返回null.

1
/**
2
 * Definition for singly-linked list.
3
 * function ListNode(val) {
4
 *     this.val = val;
5
 *     this.next = null;
6
 * }
7
 */
8

9
/**
10
 * @param {ListNode} headA
11
 * @param {ListNode} headB
12
 * @return {ListNode}
13
 */
14
var getIntersectionNode = function(headA, headB) {
15
    var p1 = headA, p2 = headB;
16
    while (p1 != p2) {
17
        p1 = p1 ? p1.next : headB;
18
        p2 = p2 ? p2.next : headA;
19
    }
20
    return p1;
21
};