文档章节

Intersection of Two Linked Lists(leetcode160)

woshixin
 woshixin
发布于 11/20 13:26
字数 245
阅读 8
收藏 0

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.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //boundary check
    if(headA == null || headB == null) {
        return null;
    }

    ListNode a = headA;
    ListNode b = headB;

    //这么写还是有点趣的,因为查完A list然后接着是 Blist,那么这样就可以不用考虑长度不等啦
    while( a != b){
        a = a == null? headB : a.next;
        b = b == null? headA : b.next;
    }

    return a;
}

public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {

    if(headA==null || headB==null) {
        return null;
    }

    Set<ListNode> set = new HashSet<ListNode>();

    ListNode a = headA;
    ListNode b = headB;

    while(a!=null) {
        set.add(a);
        a=a.next;
    }
    while(b!=null)  {
        if(set.contains(b)) {
            return b;
        }
        b = b.next;
    }
    return null;
}

© 著作权归作者所有

共有 人打赏支持
woshixin
粉丝 25
博文 283
码字总数 232377
作品 0
杭州
程序员
私信 提问
[LeetCode] Intersection of Two Linked Lists

★ 题目 https://leetcode.com/problems/intersection-of-two-linked-lists/ Write a program to find the node at which the intersection of two singly linked lists begins. For exampl......

u013553529
01/16
0
0
Leetcode 160. Intersection of Two Linked Lists

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Version 1 Version 2 Reference https://leetcode.com/problems/intersection-of-two-linked-lists/descript......

SnailTyan
10/27
0
0
单链表的交集

原题   Write a program to find the node at which the intersection of two singly linked lists begins.   For example, the following two linked lists:   begin to intersect at......

一贱书生
2016/12/26
2
0
LeetCode 160. Intersection of Two Linked Lists (两链表相交点)

原题 Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: begin to intersect at node c1. No......

dby_freedom
12/02
0
0
怎样应对IT面试与笔试-(十五)

Linked List 链表 141. Linked List Cycle 判断单链表中是否有环 使用到的数据结构:List 使用到的算法技巧:Tow Pointers 辅助指针 这道题目同样也可以用哈希表 160. Intersection of Two L...

Ice_Frog
05/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

jquery通过id显示隐藏

var $div3 = $('#div3'); 显示 $div3.show(); 隐藏 $div3.hide();

yan_liu
今天
3
0
《乱世佳人》读书笔记及相关感悟3900字

《乱世佳人》读书笔记及相关感悟3900字: 之前一直听「荔枝」,后来不知怎的转向了「喜马拉雅」,一听就是三年。上班的时候听房产,买房了以后听装修,兴之所至时听旅行,分手后听亲密关系,...

原创小博客
今天
3
0
大数据教程(9.6)map端join实现

上一篇文章讲了mapreduce配合实现join,本节博主将讲述在map端的join实现; 一、需求 实现两个“表”的join操作,其中一个表数据量小,一个表很大,这种场景在实际中非常常见,比如“订单日志...

em_aaron
今天
3
0
cookie与session详解

session与cookie是什么? session与cookie属于一种会话控制技术.常用在身份识别,登录验证,数据传输等.举个例子,就像我们去超市买东西结账的时候,我们要拿出我们的会员卡才会获取优惠.这时...

士兵7
今天
3
0
十万个为什么之为什么大家都说dubbo

Dubbo是什么? 使用背景 dubbo为什么这么流行, 为什么大家都这么喜欢用dubbo; 通过了解分布式开发了解到, 为适应访问量暴增,业务拆分后, 子应用部署在多台服务器上,而多台服务器通过可以通过d...

尾生
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部