Intersection of Two Linked Lists分享一种和答案不同的简单解法

LeetCode今天更新了一道新题，难度Easy，我做完之后在上面分享了一种解法，很好理解，和答案的思路不同。

主要思路就是跳过较长的List前面的nodes，从长度相等的地方开始一个一个的比较，直到找到Intersection或者到末尾都没有Intersection。

1.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   
2.         if (headA == null || headB == null) return null;
   
3.         int lenA = length(headA);
   
4.         int lenB = length(headB);
   
5.         int diff = Math.abs(lenA - lenB);
   
6.         while(diff > 0) {
   
7.             if (lenA > lenB) headA = headA.next;
   
8.             else headB = headB.next;
   
9.             diff--;
   
10.         }
    
11.         while (headA != null && headB != null) {
    
12.             if (headA.val == headB.val) return headA;
    
13.             headA = headA.next;
    
14.             headB = headB.next;
    
15.         }
    
16.         return null;
    
17.     }
    
18. 
    
19.     private int length(ListNode n) {
    
20.         if (n == null) return 0;
    
21.         int length = 0;
    
22.         while (n != null) {
    
23.             length++;
    
24.             n = n.next;
    
25.         }
    
26.         return length;
    
27.     }

复制代码

欢迎大家猛戳连接各种吐槽，点下左上角的Votes投个票也是可以的，感恩！ -> http://t.cn/RztHGYJ

随时欢迎正在刷题和找工作同学的骚扰，讨论解题思路，面试经验，谈人生，谈理想~可以加微博：http://www.weibo.com/freetymekiyan

祝大家感恩节快乐！

1. public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   
2.         if(headA==null || headB==null) return null;
   
3.         int lenA = 1;
   
4.         ListNode a = headA;
   
5.         for(;a.next!=null;a=a.next) lenA++;
   
6.         int lenB = 1;
   
7.         ListNode b = headB;
   
8.         for(;b.next!=null;b=b.next) lenB++; // calculate length of A and B
   
9.         if (a!=b) return null;  // no intersection
   
10.         int pad = Math.abs(lenA-lenB); // length we have to pad
    
11.         a = lenA>lenB?headA:headB;  // a is longer list
    
12.         b = a==headA?headB:headA;  // b is shorter list
    
13.         for(;pad!=0;pad--) a=a.next; // now a b are in the
    
14.         for(;a!=b;a=a.next) b=b.next; // same distance with intersection
    
15.         return a;
    
16.     }

复制代码

我也刚写完  一样的思路啊

masa 发表于 2014-11-27 17:56
我以为跟C++和Python一样该戒掉这个坏习惯了

1. public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   
2.     int lenA = length(headA), lenB = length(headB);
   
3.     // move headA and headB to the same start point
   
4.     while (lenA > lenB) {
   
5.         headA = headA.next;
   
6.         lenA--;
   
7.     }
   
8.     while (lenA < lenB) {
   
9.         headB = headB.next;
   
10.         lenB--;
    
11.     }
    
12.     // find the intersection until end
    
13.     while (headA != headB) {
    
14.         headA = headA.next;
    
15.         headB = headB.next;
    
16.     }
    
17.     return headA;
    
18. }
    

复制代码

这种写法更neat了

copper1820 发表于 2017-10-11 16:27
您好，我刚刚开始刷题 对这道题的题意理解不是很到位，想问下为什么一定要把较长的链表前面一部分跳过呢？ ...

不能用node中的数据值是否相同来判断是否为同一个node，因为两个node中可能存有相同的数据值。只能用其地址是否相同来判断是否为同一node。况且，即使真的可以用数据值来判断，你也不能“直接找到5”，因为你一开始并不知两个链表相交处的值究竟是多少。

1. if (lenA > lenB)
   
2.    while (diff--)
   
3.       A = A.next
   
4. else
   
5.    while (diff--)
   
6.       B = B.next
   

复制代码

這樣不是更好嗎？不用每次都去check A和B誰長

masa 发表于 2014-11-27 16:29
這樣不是更好嗎？不用每次都去check A和B誰長

我一开始是这么写的，确实是不用每次判断
主要是觉得不想写两边while(diff--)，这样更neat

另外受老师的影响也比较少用inline的--或++，不容易出错

masa 发表于 2014-11-27 16:29
這樣不是更好嗎？不用每次都去check A和B誰長

BTW, Java的while里面必须得是boolean

Freetymekiyan 发表于 2014-11-28 06:49
我一开始是这么写的，确实是不用每次判断
主要是觉得不想写两边while(diff--)，这样更neat

虽然是更neat但是没那么efficient吧。。

我本来是在while里面写的--diff的，后来觉得看起來太长就移到while去了……

Freetymekiyan 发表于 2014-11-28 06:52
BTW, Java的while里面必须得是boolean

我以为跟C++和Python一样{:8_253:}该戒掉这个坏习惯了

Freetymekiyan 发表于 2014-11-28 07:51
这种写法更neat了

从代码neat的角度来讲的话，算完lenA和lenB之后可以直接写  if(lenB>lenA) return getIntersectionNode(headB, headA);

这样的好处是默认A总是比B长，根本不用再做多余的判断，坏处是如果B比A长那么相当于又要返回去再算一遍各自的长度，虽然还是linear但总归要慢点儿