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

题目描述：

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

题目分析：

只是数据域相同不是公共节点。公共结点代表该节点在两个链表中的数据域和指针域都是相同的，这意味着从该公共节点开始，后面的结点都是两个链表共有的，如图：

解题思路：

思路1：

从正序比较的角度来考虑：观察上图，链表1长度大于链表2，那么公共结点绝不可能存在于链表1比链表2多出来的那些结点中。基于这种想法，我们可以先求出两个链表的长度，然后现在长链表上遍历一段距离后，再开始同时遍历长链表和短链表并进行比较。

思路2：

从倒序比较的角度考虑：这个思路比较容易理解，因为两个链表的后面一部分是重复的，我们可以建立两个栈，将两个链表分别压入两个栈：

此时如果有栈是空的，说明无公共节点，返回null；

否则，循环取两个栈的栈顶元素进行比较：如果不相等，说明公共结点为该节点的下一个结点，否则循环直至有一个栈或两个栈为空终止：终止的原因有以下几条（1）如果两个栈都为空，说明是同一个链表，返回任意链表的头结点作为公共节点。例如{1，2，3} {1，2，3}（2）如果其中一个链表为空，说明短链表的全部元素都是和长链表共有的，则返回短链表的头结点。例如{1，2，3} {2，3}

测试：两者性能差不多，运行时间和占用空间相差无几。

代码实现：

思路1

 public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

          Stack<ListNode> stack1=new Stack<ListNode>();

          Stack<ListNode> stack2=new Stack<ListNode>();

          ListNode walkNode=pHead1;

          while(walkNode!=null){

              stack1.push(walkNode);

              walkNode=walkNode.next;

          }

          walkNode=pHead2;

          while(walkNode!=null){

              stack2.push(walkNode);

              walkNode=walkNode.next;

          }

          //当两个链表都为空链表时,无公共结点,返回null

          if(stack1.size()==0||stack2.size()==0){

              return null;

          }

          while(!stack1.empty()&&!stack2.empty()){

              ListNode pop1=stack1.pop();

              ListNode pop2=stack2.pop();

              if(pop1!=pop2){

                  return pop1.next;

              }

          }

          //当两个栈同时为空时,且没有出现非公共结点,说明两个链表是完全一样的

          if(stack1.size()==0&&stack2.size()==0){

              return pHead1;          //return pHead2;

          }

         //当stack1先空时,说明链表1的所有结点和链表2都是公共的

          else if(stack1.size()==0){

              return pHead1;

          }

         //当stack2先空时,说明链表2的所有结点和链表1都是公共的

          else{

              return pHead2;

          }

     }

思路2

获取链表长度：

 public static int getLength(ListNode pHead){

         ListNode walkNode=pHead;

         int length=0;

         while(walkNode!=null){

             length++;

             walkNode=walkNode.next;

         }

         return length;

 }

寻找公共结点：

 public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

         int n1=getLength(pHead1);

         int n2=getLength(pHead2);

         int lenDiff=n1>n2?(n1-n2):(n2-n1);

         ListNode walkNode1=pHead1;

         ListNode walkNode2=pHead2;

         //将walkNode1与walkNode2对齐

         if(n1>n2){

             while(lenDiff>0){

                 lenDiff--;

                 walkNode1=walkNode1.next;

             }

         }

         else{

             while(lenDiff>0){

                 lenDiff--;

                 walkNode2=walkNode2.next;

             }

         }

         //遍历比较

         while(walkNode1!=null){

             if(walkNode1==walkNode2){

                 return walkNode1;

             }

             walkNode1=walkNode1.next;

             walkNode2=walkNode2.next;

         }

         return null;

 }

主函数测试：

public static void main(String[]args){

        ListNode phead1=new ListNode(1);

        ListNode node11=new ListNode(2);

        ListNode node12=new ListNode(3);

        ListNode phead2=new ListNode(4);

        ListNode node21=new ListNode(5);

        ListNode node13=new ListNode(6);

        ListNode node14=new ListNode(7);

        phead1.next=node11;

        node11.next=node12;

        node12.next=node13;

        node13.next=node14;

        phead2.next=node21;

        node21.next=node13;

        node13.next=node14;

        System.out.print(FindFirstCommonNode(phead1,phead2).val);

}

巴特西

两个链表的第一个公共结点——牛客offer

最新文章

热门文章