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

题目描述

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

思路

暴力法，当然是首先想到的，两层循环嘛；
链表特性，简单来说链表如果存在交点，那么后面他两一定就都一样了，也就是说交点过后的公共链是一样的
代码

基于思路2，我么你就可以懂很多脑筋，首先是，链表从头遍历到尾，从后往前遍历，因为公共链是一样的，典型的后进先出，栈就来了

   static public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//       if (pHead1==null||pHead2==null)
//           return null;
       Stack<ListNode> stack= new Stack<>();
       Stack<ListNode> stack1 = new Stack<>();
       ListNode node = null;
       while (pHead1!=null)             //把链表一压栈
       {
           stack.push(pHead1);
           pHead1=pHead1.next;
       }
       while (pHead2!=null)               //把链表二压栈
       {
           stack1.push(pHead2);
           pHead2 = pHead2.next;
       }
       /*
       检查链表是否为空，栈顶是否相同
        */
       while (!stack.isEmpty()&&!stack1.isEmpty()&&stack.peek()==stack1.peek())
       {
           node=stack.peek();
           stack.pop();
           stack1.pop();
       }
        return  node;
    }

栈的方法是基于后进先出，那么我们可不可以直接遍历呢？
由于公共链是一样的，所以做多就是一条链比另一条长那么一点；所以你知道的，把这点长度差消除

static public ListNode FindFirstCommonNode1(ListNode pHead1, ListNode pHead2)
   {
       if (pHead1==null||pHead2 ==null)
           return  null;
       int length1 = 0 ;
       int length2 = 0;
       ListNode node1 = pHead1;
       ListNode node2 = pHead2;
       while (pHead1!=null)        //链表一长度
       {
           length1++;
           pHead1=pHead1.next;
       }
       while (pHead2!=null)          //链表二长度
       {
           length2++;
           pHead2=pHead2.next;
       }
       while (length1>length2)        //消除长度差异
       {
           node1=node1.next;
           length1--;
       }
       while (length2>length1)          //消除长度差异
       {
           node2 = node2.next;
           length2--;
       }
       while (node1!=null&&node2!=null)    //找公共点
       {
           if (node1==node2)
               break;
           node1=node1.next;
           node2 = node2.next;
       }
       return node1;
   }

我们看到上面的方法是在干嘛呢？消除差异，于是就有了超厉害的代码喽

static public ListNode FindFirstCommonNode2(ListNode pHead1,ListNode pHead2)
  {
      ListNode node1 = pHead1;
      ListNode node2 = pHead2;
      while ( node1!=null)
      {
       /*
          简单来说，相当于链表一和链表二对一个node都遍历过，
          所以长度肯定是一样的
           */
          node1=(node1==null?pHead2:node1.next);
          node2=(node2==null?pHead1:node2.next);
      }
      return node1;
  }

收获

抓住重点，链表的特性，单链表需要从头遍历，公共链表一样等特性

2017-04-02