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

2021/9/25 23:41:57

本文主要是介绍剑指 Offer 52. 两个链表的第一个公共节点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在这里插入图片描述
思路:
由于两条链表在相交节点后面的部分完全相同,因此我们可以先对两条链表进行遍历,分别得到两条链表的长度,并计算差值 d。
让长度较长的链表先走 d 步,然后两条链表同时走,第一个相同的节点即是节点
作者:AC_OIer
链接:https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/gong-shui-san-xie-zhao-liang-tiao-lian-b-ifqw/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

/**
 * 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) {
    int la=0, lb=0;
    ListNode *a = headA, *b=headB;
    while(a){
        a = a->next;
        la++;
    }

    while(b){
        b = b->next;
        lb++;
    }

    int d = lb - la;  // 链表长度
    if(d<0){
        d = -d;
    }

    if(lb>la){
        while(d--)
            headB=headB->next;
    }else{
        while(d--)
            headA=headA->next;
    }

    while(headA!=headB){
        //  一起走,知道两个指针相同(地址值相同,不是指针所指的值)
        headA=headA->next;
        headB=headB->next;
    }
    
    return headA;

    }
};



这篇关于剑指 Offer 52. 两个链表的第一个公共节点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程