一、题目内容

image.png

二、题解

解法1：

思路

分别计算两个链表长度作差，减去差值后遍历链表最后一定相等，null，或者相交

代码

  1. public class Solution {
  2.     public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
  3.         ListNode a = pHead1;
  4.         ListNode b = pHead2;
  5.         int lena = 0,lenb = 0;
  6.         while(a!=null){
  7.             a = a.next;
  8.             lena++;
  9.         }
  10.         while(b!=null){
  11.             b = b.next;
  12.             lenb++;
  13.         }
  14.         int d = lena-lenb;
  15.         if(d>0){
  16.             while(d-->0){
  17.                 pHead1 = pHead1.next;
  18.             }
  19.         }else{
  20.             while(d++<0){
  21.                 pHead2 = pHead2.next;
  22.             }
  23.         }
  25.         while(pHead1!=pHead2){
  26.             pHead1 = pHead1.next;
  27.             pHead2 = pHead2.next;
  28.         }
  29.         return pHead1;
  30.     }
  31. }

解法2：

思路

a+(b-c) = b+(a-c) => a+b-c = b+a-c
c>0：相交，a=b
c=0：不相交，a=b=null

代码

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode a = pHead1;
        ListNode b = pHead2;
        while(a!=b){
            a = a!=null? a.next:pHead2;
            b = b!=null? b.next:pHead1;
        }
        return a;
    }
}