剑指Offer: 两个链表的第一个公共结点

待我称王封你为后i 2023-07-18 14:11 1阅读 0赞

##### 1. 题目描述 #####

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）  
原题传送门：[link][].

##### 2. 提取关键词 #####

哈希数组

##### 3. 思路 #####

*  首先将两个指针全部遍历到链表的尾部
 *  然后长链表的长度len1减去短链表len2的长度得len1-len2
 *  然后设置短链表指针指针从头出发，长链表指针从len1-len2处出发
 *  第一个交点便是他们第一个公共节点

##### 4. 代码（Java） #####

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
          if(pHead1==null||pHead2==null){
               return null;
           }
            ListNode head1=pHead1,head2=pHead2;
            int len1=0,len2=0;
            while(head1!=null){
                head1=head1.next;
                len1++;
            }
            while(head2!=null){
                head2=head2.next;
                len2++;
            }
            head1=pHead1;
            head2=pHead2;
            int sub_value1=len2-len1;
            int sub_value2=len1-len2;
            if(sub_value1>0){
                while(sub_value1>0){
                 head2=head2.next;
                sub_value1--;  
                }
            }
            if(sub_value2>0){
               while(sub_value2>0){
                 head1=head1.next;
                sub_value2--;  
                } 
            }
            while(head1!=null)
            {
                if(head1.val==head2.val){
                    return head1;
                }
                head1=head1.next;
                head2=head2.next;
            }
           return null;
        }
    }

##### 5.复杂度 #####

*  暂无

##### 6. 知识积累 #####

*  暂无

[link]: https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&tPage=2&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking