找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2390|回复: 2
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Intersection of Two Linked Lists 】【刷题第一弹】

[复制链接]

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 11-27-2014 07:55 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
Leetcode:https://oj.leetcode.com/problems/intersection-of-two-linked-lists/汇总帖:http://www.meetqun.com/thread-703-1-1.html
1. 题目:
Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2                   ↘                     c1 → c2 → c3                   ↗            B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.
2. 分析
很多书上都有这道题目,可以先计算出两个链表的长度,然后将长的链表向前移动长度差的距离,得到新的起点,这样从两个链表的新的起点开始向后
遍历链表,直到尾部或者是两者相等
3. 复杂度
相当于每个链表要访问2次,因此时间复杂度O(n),空间复杂度O(1)
4. 代码

  1.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  2.         if(headA == nullptr || headB == nullptr) return nullptr;
  3.         
  4.         int la = 0;
  5.         for(ListNode *p = headA; p != nullptr; p = p->next){
  6.             la++;
  7.         }
  8.         
  9.         int lb = 0;
  10.         for(ListNode *p = headB; p != nullptr; p = p->next){
  11.             lb++;
  12.         }
  13.         
  14.         int diff = 0;
  15.         ListNode *lp = nullptr;
  16.         ListNode *sp = nullptr;
  17.         if(la >= lb){
  18.             diff = la - lb;
  19.             lp = headA;
  20.             sp = headB;
  21.         }
  22.         else{
  23.             diff = lb - la;
  24.             lp = headB;
  25.             sp = headA;            
  26.         }
  27.         
  28.         for(int i = 0; i < diff; i++){
  29.             lp = lp->next;
  30.         }
  31.         
  32.         while(lp != nullptr && sp != nullptr){
  33.             if(lp == sp) return lp;
  34.             else{
  35.                 lp = lp->next;
  36.                 sp = sp->next;
  37.             }
  38.         }
  39.         
  40.         return nullptr;
  41.     }
复制代码
5.相关题目


补充内容 (11-28-2014 05:06 AM):
用hash表也能达到O(n)的时间复杂度,我觉得思路不用局限,就算不是最好的,分享出来也能开阔思路,效果可能比只有一个答案的要好

1

主题

0

精华

295

积分

高级会员

Rank: 3Rank: 3

积分
295
发表于 11-27-2014 09:53 PM | 显示全部楼层
思路:
1. 从头遍历两个链表;
2. 短的到尾部后,新的指针指向长链表头部,新指针随原来的node一起遍历长链表到尾部
3. 短链表从头部随长链表新指针一起遍历到尾部

时间复杂度O(m+n),空间复杂度O(1)
m,n为链表A,B的长度

  1. public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  2.         if(headA==null || headB==null) return null;
  3.         
  4.         //iterate the lists
  5.         ListNode nodeA = headA;
  6.         ListNode nodeB = headB;
  7.         while(nodeA!=null && nodeB!=null){
  8.             nodeA = nodeA.next;
  9.             nodeB = nodeB.next;
  10.         }

  11.         ListNode longList, shortList;
  12.         if(nodeA!=null){
  13.             longList = headA;
  14.             shortList = headB;
  15.         } else{
  16.             longList = headB;
  17.             shortList = headA;
  18.             nodeA = nodeB;
  19.         }
  20.         
  21.         while(nodeA!=null){
  22.             nodeA = nodeA.next;
  23.             longList = longList.next;
  24.         }
  25.         
  26.         while(longList!=null){
  27.             if(longList==shortList) return longList;
  28.             longList = longList.next;
  29.             shortList = shortList.next;
  30.         }
  31.         return null;
  32.     }
复制代码
回复 支持 反对

使用道具 举报

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
 楼主| 发表于 11-28-2014 01:21 AM | 显示全部楼层
发个和楼上思路一样的,设A,B链表的非相同节点的个数分别为la,lb,公共节点数为lc,则分别从链表的起点出发,到达自身的尾节点后转向另一个链表的头结点,继续向前,最后达到第一个公共节点,两条路径总共的经历的节点数目均为la+lb+lc,因此采用这种方式可以获得公共节点。
  1.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  2.         if(headA == nullptr || headB == nullptr) return nullptr;
  3.         
  4.         bool flag_a = true, flag_b = true;
  5.         for(ListNode *pa = headA, *pb = headB; pa && pb; ){
  6.             if(pa == pb) return pa;
  7.             
  8.             ListNode *pre_pa = pa;
  9.             pa = (pa->next == nullptr && flag_a) ? headB : pa->next;
  10.             flag_a = ((pre_pa->next == nullptr && flag_a) || !flag_a) ? false : true;

  11.             ListNode *pre_pb = pb;
  12.             pb = (pb->next == nullptr && flag_b) ? headA : pb->next;
  13.             flag_b = ((pre_pb->next == nullptr && flag_b) || !flag_b) ? false : true;
  14.         }
  15.         
  16.         return nullptr;
  17.     }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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