首页 > 代码库 > 两个链表的第一个公共结点

两个链表的第一个公共结点

题目

  输入两个链表,找出它们的第一个公共结点。

 

分析

  首先分别遍历list1和list2,得到两个链表的长度count1和count2,同时,判断两个链表的尾指针是否相同,如果不同,说明两个链表不存在公共结点;如果相同,则继续......。比较count1和count2,如果count1>count2,让指针n1向前移动count1-count2;否则让指针n2向前移动count2-count1。最后,两个指针同时向前移动,直到两个指针指向的结点相同,并返回。

 

代码

 1   public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2){
 2         int count1 = 0, count2 = 0;
 3         ListNode node1 = pHead1, node2 = pHead2;
 4         while(node1!=null){
 5             count1++;
 6             node1 = node1.next;
 7         }
 8         while(node2!=null){
 9             count2++;
10             node2 = node2.next;
11         }
12         if(node1!=node2)
13             return null;
14         ListNode n1 = pHead1, n2 = pHead2;
15         if(count1>count2){
16             for(int i=0;i<count1-count2;i++){
17                 n1 = n1.next;
18             }
19         }
20         else{
21             for(int i=0;i<count2-count1;i++){
22                 n2 = n2.next;
23             }
24         }
25         while(n1!=n2){
26             n1 = n1.next;
27             n2 = n2.next;
28         }
29         return n1;
30     }

 

两个链表的第一个公共结点