LeetCode 160.Intersection of Two Linked Lists (相交链表)

雨点打透心脏的1/2处 2022-05-10 14:42 113阅读 0赞

题目描述：

编写一个程序，找到两个单链表相交的起始节点。

例如，下面的两个链表**：**

A:          a1 → a2
                       ↘
                         c1 → c2 → c3
                       ↗            
    B:     b1 → b2 → b3

在节点 c1 开始相交。

**注意：**

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

AC C++ Solution:

解题思路：两链表相交的话，后面部分一定是相同的，所以先计算两链表的长度差n；

让长链表先走n步，然后两链表同时遍历，比较每个对应节点。

class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            
            ListNode *pa = headA, *pb = headB;
            int lengthA = 0, lengthB = 0;
            
            while(pa)   { pa = pa->next; lengthA++; }
            while(pb)   { pb = pb->next; lengthB++; }
            
            
            if(lengthA <= lengthB) {
                pa = headA; pb = headB;
                
                int n = lengthB-lengthA;
                while(n) { pb = pb->next; n--; }
            }
            else {
                pa = headA; pb = headB;
                
                int n = lengthA-lengthB;
                while(n) { pa = pa->next; n--; }
            }
            
            while(pa != pb) {
                pa = pa->next;
                pb = pb->next;
            }
            
            return pa;
        }
    };