剑指 Offer 52 两个链表的第一个公共节点

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-27 11:08:36
    编辑于：2022-02-27 11:25:30
    浏览量：769

概述

https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

https://leetcode.com/problems/intersection-of-two-linked-lists/

暴力遍历

两个链表分别先遍历一遍记录个数并判断是否存在公共节点，之后较长的链表先走，等到剩余长度与较短的链表相同时两个一起开始，直到找到目标节点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto dummyHeadA = new ListNode();
        dummyHeadA->next = headA;
        auto an = dummyHeadA;
        int ac = 0;
        while (an->next) {
            an = an->next;
            ac ++;
        }
        auto dummyHeadB = new ListNode();
        dummyHeadB->next = headB;
        auto bn = dummyHeadB;
        int bc = 0;
        while (bn->next) {
            bn = bn->next;
            bc ++;
        }
        if (an != bn) return nullptr;
        an = dummyHeadA;
        bn = dummyHeadB;
        if (ac < bc) {
            while (ac < bc) {
                bc --;
                bn = bn->next;
            }
        } else if (ac > bc) {
            while (ac > bc) {
                ac --;
                an = an->next;
            }
        }
        while (an != bn) {
            an = an->next;
            bn = bn->next;
        }
        
        return an;
    }
};

拼接法

拼接的时候，不要采取给 next 指针赋值的形式！不然将导致死循环。

/**
 * 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) {
        if (!headA || !headB) return nullptr;
        auto a = headA;
        auto b = headB;
        bool flagA = true;
        bool flagB = true;
        while (a != b) {
            if (!a && flagA) {
                flagA = false;
                a = headB;
            }
            if (!b && flagB) {
                flagB = false;
                b = headA;
            }
            if (a == b) break;
            a = a->next;
            b = b->next;
        }
        return a;
    }
};

Links: sword-offer-52