廖家龙的博客网站
剑指Offer_52_两个链表的第一个公共节点
廖家龙 用心听，不照做
  2019-06-30 14:53:00   2024-07-19 11:18:10    1.1k 字  4 分钟

❗️LeetCode_160_相交链表

❗️注意本题与剑指Offer_68_树中两个节点的最低公共祖先有联系

题目描述：

1
2
3
4
5
6
7
8
9
10
11
输入两个链表，找出它们的第一个公共节点。

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

注意：
1. 如果两个链表没有交点，返回 null.
2. 在返回结果后，两个链表仍须保持原有的结构。
3. 可假定整个链表结构中没有循环。
4. 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解法1：

用蛮力法，在第一个链表上顺序遍历每个节点，每遍历到一个节点，就在第二个链表上顺序遍历每个节点。如果在第二个链表上有一个节点和第一个链表上的节点一样，则说明两个链表在这个节点上重合，于是就找到了它们的公共节点。如果第一个链表的长度为m，第二个链表的长度为n，那么显然该方法的时间复杂度是O(mn)

解法2：

如果两个链表有公共节点，那么公共节点出现在两个链表的尾部，如果我们从两个链表的尾部开始往前比较，那么最后一个相同的节点就是我们要找的节点。于是我们就能想到用栈的特点来解决这个问题：分别把两个链表的节点放入两个栈里，这样两个链表的尾节点就位于两个栈的栈顶，接下来比较两个栈顶的节点是否相同，如果相同，则把栈顶弹出接着比较下一个栈顶，直到找到最后一个相同的节点。空间复杂度为O(m+n)，时间复杂度也是O(m+n)，和蛮力法相比，时间效率得到了提高，相当于用空间消耗换取了时间效率

⭐️问题：当两个链表的长度不相同时，如果我们从头开始遍历，那么到达尾节点的时间就不一致

解法3：

首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历的时候，在较长的链表上先走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的第一个公共节点。时间复杂度为O(m+n)，但我们不再需要辅助栈，因此提高了空间效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    //返回链表的长度
    unsigned int GetListLength(ListNode* pHead) {

        unsigned int nLength = 0;
        ListNode* pNode = pHead;

        while (pNode != NULL) {

            ++nLength;
            pNode = pNode -> next;
        }

        return nLength;
    }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
        unsigned int nLength1 = GetListLength(headA);  //headA的长度
        unsigned int nLength2 = GetListLength(headB);  //headB的长度
        int nLengthDif = nLength1 - nLength2;  //两个链表之差（假设headA > headB）

        ListNode* pListHeadLong = headA;
        ListNode* pListHeadShort = headB;

        if (nLength2 > nLength1) {
            pListHeadLong = headB;
            pListHeadShort = headA;
            nLengthDif = nLength2 - nLength1;
        }

        //先在长链表上走几步，再同时在两个链表上遍历
        for (int i = 0;i < nLengthDif;i++) {
            pListHeadLong = pListHeadLong -> next;
        }

        while (pListHeadLong != NULL && 
               pListHeadShort != NULL && 
               pListHeadLong != pListHeadShort) {

            pListHeadLong = pListHeadLong -> next;
            pListHeadShort = pListHeadShort ->next;
        }

        //得到第一个公共结点
        ListNode* pFirstCommonNode = pListHeadLong;
        
        return pFirstCommonNode;
    }
};

解法4：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
        ListNode* l1 = headA,*l2 = headB;

        //假设链表A的头节点到相交点的距离是a，链表B的头节点到相交点的距离是b，相交点到链表终点的距离为c
        //我们使用两个指针，分别指向两个链表的头节点，并以相同的速度前进，若到达链表结尾，则移动到另一条链表的头节点继续前进。按照这种前进方法，两个指针会在a+b+c次前进后同时到达相交节点
        while (l1 != l2) {

            l1 = l1 ? l1->next : headB;
            l2 = l2 ? l2->next : headA;
        }

        return l1;
    }
};
  1. 1. 题目描述：
    1. 1.1. 解法1：
    2. 1.2. 解法2：
    3. 1.3. 解法3：
    4. 1.4. 解法4：
  1. 1. 题目描述：
    1. 1.1. 解法1：
    2. 1.2. 解法2：
    3. 1.3. 解法3：
    4. 1.4. 解法4：