剑指offer系列62---两个链表的公共结点

【题目】输入两个链表，找出它们的第一个公共结点。
* 【思路】1 获取两链表的长度；
* 2 让长的链表先走n步后此时走到短链表起始位置；
* 3 两链表同时遍历，直至相同，这时返回第一个公共结点。

 1 package com.exe11.offer;
 2 
 3 /**
 4  * 【题目】输入两个链表，找出它们的第一个公共结点。
 5  * 【思路】1 获取两链表的长度；
 6  *           2 让长的链表先走n步后此时走到短链表起始位置；
 7  *           3 两链表同时遍历，直至相同，这时返回第一个公共结点。
 8  * @author WGS
 9  *
10  */
11 public class CommonListNode {
12 
13     static class ListNode{
14         int val;
15         ListNode next=null;
16         public ListNode(int val){
17             this.val=val;
18         }
19     }
20     public ListNode getCommonNode(ListNode pHead1,ListNode pHead2){
21         if(pHead1==null ||pHead2==null)
22             return null;
23         //1 获取两个链表长度
24         int len1=getListNodeLength(pHead1);
25         int len2=getListNodeLength(pHead2);
26         //2 比较长度
27         int difVal=len1-len2;
28         ListNode longListNode=pHead1;
29         ListNode shortListNode=pHead2;//假设pHead1长，pHead2短
30         if(difVal<0){//len1<len2,pHead2长
31             longListNode=pHead2;
32             shortListNode=pHead1;
33             difVal=len2-len1;
34         }
35         //3 让长的先走n（difVal）步
36         for(int i=0;i<difVal;i++){
37             longListNode=longListNode.next;
38         }
39         //4 再一起走
40         while(longListNode!=null && shortListNode!=null &&(longListNode.val!=shortListNode.val)){
                 //当碰到相同值即为公共结点，跳出循环

　　　　　　　　　　if(shortNode.val==longNode.val){
　　　　　　　　　　　　return longNode;
　　　　　　　　　　　}

41             longListNode=longListNode.next;
42             shortListNode=shortListNode.next;
43         }
44         //当碰到相同值即为公共结点，跳出循环
45         ListNode commonNode=longListNode;
46         /*if(longListNode.val==shortListNode.val){
47             commonNode=shortListNode;//返回 公共结点
48         }*/
49         
50         return commonNode;
51         
52     }
53     //获取链表长度
54     private int getListNodeLength(ListNode pHead){
55         ListNode node=pHead;
56         int len=0;
57         while(node!=null){
58             len++;
59             node=node.next;
60         }
61         return len;        
62     }
63     
64     
65     
66     
67     
68     
69     public static void main(String[] args) {
70           ListNode pHead1 = new ListNode(1);
71             ListNode node1 = new ListNode(2);
72             ListNode node2 = new ListNode(3);
73             ListNode node3 = new ListNode(4);
74            // ListNode node4 = new ListNode(7);
75             pHead1.next = node1;
76             node1.next = node2;
77             node2.next = node3;
78             //node3.next = node4;
79             
80             ListNode pHead2 = new ListNode(5);
81             ListNode node5 = new ListNode(6);
82             ListNode node6 = new ListNode(7);
83            // ListNode node7 = new ListNode(7);
84             pHead2.next = node5;
85             node5.next = node6;
86            // node6.next = node7;
87             
88             CommonListNode c=new CommonListNode();
89             ListNode node=c.getCommonNode(pHead1, pHead2);
90             System.out.println(node);
91 
92     }
93 
94 }

或者，用一个集合先把第一个链表所有值加入，再依次跟第二个链表值比较，当有第一个相同时即为第一个公共结点。

 1 package com.exe11.offer;
 2 
 3 import java.util.HashMap;
 4 
 5 /**
 6  * 【题目】输入两个链表，找出它们的第一个公共结点。
 7  * 【思路】1 获取两链表的长度；
 8  *           2 让长的链表先走n步后此时走到短链表起始位置；
 9  *           3 两链表同时遍历，直至相同，这时返回第一个公共结点。
10  * @author WGS
11  *
12  */
13 public class CommonListNode2 {
14 
15     static class ListNode{
16         int val;
17         ListNode next=null;
18         public ListNode(int val){
19             this.val=val;
20         }
21     }
22     public ListNode getCommonNode(ListNode pHead1,ListNode pHead2){
23         HashMap<ListNode,Integer> map=new HashMap<>();
24         //先把pHead1值全部添加至集合中
25         while(pHead1!=null){
26             map.put(pHead1, 1);
27             pHead1=pHead1.next;
28         }
29         //
30         //ListNode commonNode=null;
31         while(pHead2!=null){
32             Integer node=map.get(pHead2);
33             if(node!=null)
34                 return pHead2;
35             pHead2=pHead2.next;
36         }
37         return null;
38         
39     }    
40     
41     
42     
43     
44     public static void main(String[] args) {
45           ListNode pHead1 = new ListNode(1);
46             ListNode node1 = new ListNode(2);
47             ListNode node2 = new ListNode(3);
48             ListNode node3 = new ListNode(4);
49            // ListNode node4 = new ListNode(7);
50             pHead1.next = node1;
51             node1.next = node2;
52             node2.next = node3;
53             //node3.next = node4;
54             
55             ListNode pHead2 = new ListNode(5);
56             ListNode node5 = new ListNode(6);
57             ListNode node6 = new ListNode(7);
58            // ListNode node7 = new ListNode(7);
59             pHead2.next = node5;
60             node5.next = node6;
61            // node6.next = node7;
62             
63             CommonListNode2 c=new CommonListNode2();
64             ListNode node=c.getCommonNode(pHead1, pHead2);
65             System.out.println(node.val);
66 
67     }
68 
69 }