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

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

 package com.exe11.offer;

 /**

  * 【题目】输入两个链表，找出它们的第一个公共结点。

  * 【思路】1 获取两链表的长度；

  *           2 让长的链表先走n步后此时走到短链表起始位置；

  *           3 两链表同时遍历，直至相同，这时返回第一个公共结点。

  * @author WGS

  *

  */

 public class CommonListNode {

     static class ListNode{

         int val;

         ListNode next=null;

         public ListNode(int val){

             this.val=val;

         }

     }

     public ListNode getCommonNode(ListNode pHead1,ListNode pHead2){

         if(pHead1==null ||pHead2==null)

             return null;

         //1 获取两个链表长度

         int len1=getListNodeLength(pHead1);

         int len2=getListNodeLength(pHead2);

         //2 比较长度

         int difVal=len1-len2;

         ListNode longListNode=pHead1;

         ListNode shortListNode=pHead2;//假设pHead1长，pHead2短

         if(difVal<0){//len1<len2,pHead2长

             longListNode=pHead2;

             shortListNode=pHead1;

             difVal=len2-len1;

         }

         //3 让长的先走n（difVal）步

         for(int i=0;i<difVal;i++){

             longListNode=longListNode.next;

         }

         //4 再一起走

         while(longListNode!=null && shortListNode!=null &&(longListNode.val!=shortListNode.val)){
                 //当碰到相同值即为公共结点，跳出循环

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

             longListNode=longListNode.next;

             shortListNode=shortListNode.next;

         }

         //当碰到相同值即为公共结点，跳出循环

         ListNode commonNode=longListNode;

         /*if(longListNode.val==shortListNode.val){

             commonNode=shortListNode;//返回 公共结点

         }*/

         return commonNode;

     }

     //获取链表长度

     private int getListNodeLength(ListNode pHead){

         ListNode node=pHead;

         int len=0;

         while(node!=null){

             len++;

             node=node.next;

         }

         return len;

     }

     public static void main(String[] args) {

           ListNode pHead1 = new ListNode(1);

             ListNode node1 = new ListNode(2);

             ListNode node2 = new ListNode(3);

             ListNode node3 = new ListNode(4);

            // ListNode node4 = new ListNode(7);

             pHead1.next = node1;

             node1.next = node2;

             node2.next = node3;

             //node3.next = node4;

             ListNode pHead2 = new ListNode(5);

             ListNode node5 = new ListNode(6);

             ListNode node6 = new ListNode(7);

            // ListNode node7 = new ListNode(7);

             pHead2.next = node5;

             node5.next = node6;

            // node6.next = node7;

             CommonListNode c=new CommonListNode();

             ListNode node=c.getCommonNode(pHead1, pHead2);

             System.out.println(node);

     }

 }

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

 package com.exe11.offer;

 import java.util.HashMap;

 /**

  * 【题目】输入两个链表，找出它们的第一个公共结点。

  * 【思路】1 获取两链表的长度；

  *           2 让长的链表先走n步后此时走到短链表起始位置；

  *           3 两链表同时遍历，直至相同，这时返回第一个公共结点。

  * @author WGS

  *

  */

 public class CommonListNode2 {

     static class ListNode{

         int val;

         ListNode next=null;

         public ListNode(int val){

             this.val=val;

         }

     }

     public ListNode getCommonNode(ListNode pHead1,ListNode pHead2){

         HashMap<ListNode,Integer> map=new HashMap<>();

         //先把pHead1值全部添加至集合中

         while(pHead1!=null){

             map.put(pHead1, 1);

             pHead1=pHead1.next;

         }

         //

         //ListNode commonNode=null;

         while(pHead2!=null){

             Integer node=map.get(pHead2);

             if(node!=null)

                 return pHead2;

             pHead2=pHead2.next;

         }

         return null;

     }

     public static void main(String[] args) {

           ListNode pHead1 = new ListNode(1);

             ListNode node1 = new ListNode(2);

             ListNode node2 = new ListNode(3);

             ListNode node3 = new ListNode(4);

            // ListNode node4 = new ListNode(7);

             pHead1.next = node1;

             node1.next = node2;

             node2.next = node3;

             //node3.next = node4;

             ListNode pHead2 = new ListNode(5);

             ListNode node5 = new ListNode(6);

             ListNode node6 = new ListNode(7);

            // ListNode node7 = new ListNode(7);

             pHead2.next = node5;

             node5.next = node6;

            // node6.next = node7;

             CommonListNode2 c=new CommonListNode2();

             ListNode node=c.getCommonNode(pHead1, pHead2);

             System.out.println(node.val);

     }

 }