一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 5441|回复: 13
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
Freetymekiyan 发表于 2014-11-28 00:55:12 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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.     private int length(ListNode n) {
  19.         if (n == null) return 0;
  20.         int length = 0;
  21.         while (n != null) {
  22.             length++;
  23.             n = n.next;
  24.         }
  25.         return length;
  26.     }
复制代码

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

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

祝大家感恩节快乐!




Adeath 发表于 2014-11-28 02:11:54 | 显示全部楼层
  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-28 05:29:17 | 显示全部楼层
本帖最后由 masa 于 2014-11-28 05:32 编辑
  1. if (lenA > lenB)
  2.    while (diff--)
  3.       A = A.next
  4. else
  5.    while (diff--)
  6.       B = B.next
复制代码
這樣不是更好嗎?不用每次都去check A和B誰長
回复 支持 反对

使用道具 举报

 楼主| Freetymekiyan 发表于 2014-11-28 06:49:08 | 显示全部楼层
masa 发表于 2014-11-27 16:29
這樣不是更好嗎?不用每次都去check A和B誰長

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

另外受老师的影响也比较少用inline的--或++,不容易出错
回复 支持 反对

使用道具 举报

 楼主| Freetymekiyan 发表于 2014-11-28 06:52:03 | 显示全部楼层
masa 发表于 2014-11-27 16:29
這樣不是更好嗎?不用每次都去check A和B誰長

BTW, Java的while里面必须得是boolean
回复 支持 反对

使用道具 举报

masa 发表于 2014-11-28 06:54:39 | 显示全部楼层
Freetymekiyan 发表于 2014-11-28 06:49
我一开始是这么写的,确实是不用每次判断
主要是觉得不想写两边while(diff--),这样更neat

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

我本来是在while里面写的--diff的,后来觉得看起來太长就移到while去了……
回复 支持 反对

使用道具 举报

masa 发表于 2014-11-28 06:56:04 | 显示全部楼层
Freetymekiyan 发表于 2014-11-28 06:52
BTW, Java的while里面必须得是boolean

我以为跟C++和Python一样该戒掉这个坏习惯了
回复 支持 反对

使用道具 举报

 楼主| Freetymekiyan 发表于 2014-11-28 07:51:20 | 显示全部楼层
本帖最后由 Freetymekiyan 于 2014-11-27 18:55 编辑
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了
回复 支持 反对

使用道具 举报

masa 发表于 2014-11-28 08:00:11 | 显示全部楼层
回复 支持 反对

使用道具 举报

tbu 发表于 2014-11-28 08:31:02 | 显示全部楼层
从代码neat的角度来讲的话,算完lenA和lenB之后可以直接写  if(lenB>lenA) return getIntersectionNode(headB, headA);

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

使用道具 举报

sodasun 发表于 2014-11-28 12:20:08 | 显示全部楼层
楼主问你一下 为什么 if (headA.val == headB.val) return headA;就能返回了呢 有没有可能相同高度的两个点的值相同但是next不相同呢?
回复 支持 反对

使用道具 举报

 楼主| Freetymekiyan 发表于 2014-11-29 03:18:12 | 显示全部楼层
tbu 发表于 2014-11-27 19:31
从代码neat的角度来讲的话,算完lenA和lenB之后可以直接写  if(lenB>lenA) return getIntersectionNode(hea ...

是的,swap headA和headB的写法我也很喜欢
回复 支持 反对

使用道具 举报

 楼主| Freetymekiyan 发表于 2014-11-29 03:21:19 | 显示全部楼层
sodasun 发表于 2014-11-27 23:20
楼主问你一下 为什么 if (headA.val == headB.val) return headA;就能返回了呢 有没有可能相同高度的两个点 ...

你说的对,逻辑上value相等和node相等不等价,只是在这道里里面我们可以这样简化
相当于题目默认了没到交叉点前面的node value都不一样

如果真的要判断是同一node,类似headA.equals(headB)
回复 支持 反对

使用道具 举报

sodasun 发表于 2014-11-29 06:04:37 | 显示全部楼层
Freetymekiyan 发表于 2014-11-29 03:21
你说的对,逻辑上value相等和node相等不等价,只是在这道里里面我们可以这样简化
相当于题目默认了没到 ...

谢谢楼主 happy thanksgiving~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 05:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表