- 浏览: 173795 次
- 性别:
- 来自: 济南
文章分类
最新评论
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.
给定两个链表,判断它们是否交叉,如果没有交叉返回空,如果有交叉,返回交叉的起始点。我们遍历两个链表,判断元素是否相等,但是前提是两个链表长度相同。题目中的两个链表长度不同,我们可以同时遍历两个链表A,B,当A链表为空时让它指向B链表的头结点,当B链表为空时,让B链表指向A链表的头结点(这种情况是A链表比B链表短),同理A链表比B链表长的情况。代码如下:
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.
给定两个链表,判断它们是否交叉,如果没有交叉返回空,如果有交叉,返回交叉的起始点。我们遍历两个链表,判断元素是否相等,但是前提是两个链表长度相同。题目中的两个链表长度不同,我们可以同时遍历两个链表A,B,当A链表为空时让它指向B链表的头结点,当B链表为空时,让B链表指向A链表的头结点(这种情况是A链表比B链表短),同理A链表比B链表长的情况。代码如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode curA = headA; ListNode curB = headB; while(curA != curB) { curA = (curA == null) ? headB : curA.next; curB = (curB == null) ? headA : curB.next; } return curA; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 228You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 343Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 335Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 513Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 431Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 622Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 534Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 862Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 556Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 765Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 736You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 630For a undirected graph with tre ...
相关推荐
leetcode 2 sum c LeetCode 帮助文档 帮助文档存放在Help文件夹下。...Intersection of Two Linked Lists 203 Easy Remove Linked List Elements no 206 Easy Reverse Linked List 234 Easy Palindrome Linked List
两个大数组的交集
350. 两个数组的交集II Intersection of Two Arrays II思路一:排序找交集,从小到大遍历,遇到相等的就加到ans中,然后都看下一
371 | [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/) | [C++](./C++/sum-of-two-integers.cpp) [Python](./Python/sum-of-two-integers.py) | _O(1)_ | _O(1)_ | Easy | LintCode | ...
The topics include Cycle and Intersection Detection in Linked Lists, Finding the First Node of a Cycle, Generation of Permutations and Combinations with and without Repetition, Reconstruction of ...
smarter-decisions-intersection-of-iot.pdf
Randy B. Lee & David A. Fredricks的intersection of parametric surfaces and plane
信息安全_数据安全_Intersection of Data Breach Noti 常规渗透 可信编译 态势感知 安全审计 企业安全
(2)The Intersection of two Sets (overload operator *,*=) (3)The Difference of two Sets (overload operator -) (4)Add an element to a Set (5)Delete an element from a Set (6)Get the element which has the...
Verse Communications84 La EspiralOrinda, CA 94563 USAnate@verse.comABSTRACTSorted lists of integers are commonly used in inverted in- dexes and database systems. They are often compres
Intersection-of-Two-Arrays-LeetCode
(2)The Intersection of two Sets (overload operator *,*=) (3)The Difference of two Sets (overload operator -) (4)Add an element to a Set (5)Delete an element from a Set (6)Get the element which has...
(2)The Intersection of two Sets (overload operator *,*=) (3)The Difference of two Sets (overload operator -) (4)Add an element to a Set (5)Delete an element from a Set (6)Get the element...
CIRCLEINTERSECT Finds intersection of two circles.Function to return the intersection points between two circles given their centres and radi.
多支链并联机器人自由度分析与驱动器布置,卜王辉,刘振宇,为了克服经典CGK自由度计算公式在处理多约束多支链并联机器人的例外情况,本文提出了一种新的基于螺旋空间交集运算的机构自由度计
leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起...160.Intersection of Two Linke
You have two sets of data, two lists, and you want to compare them. We can demonstrate this problem with the awesome power of a Venn diagram: The Venn diagram has three interesting areas: the bit on ...
A.1 The Intersection of Two Vector Spaces 459 A.2 The Sum of Two Vector Spaces 460 A.3 The Cartesian Product of Two Vector Spaces 461 A.4 The Tensor Product of Two Vector Spaces 461 A.5 The Kronecker ...
This volume discusses a construction situated at the intersection of two different mathematical fields: Abstract harmonic analysis, understood as the theory of group representations and their ...
leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。 我的个人网站: 分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您...Intersection of Two Linke