首页 > 代码库 > LeetCode Intersection of Two Linked Lists
LeetCode 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:
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.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.
如果没有要求此题很简单。用hashset就可以。
但是题目要求 in O(n) time and use only O(1) memory。
可以先遍历两个链表，把他们的长度变为一样长。然后逐个比较。
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * }10 * }11 */12 public class Solution {13 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {14 int a=0, b = 0;15 ListNode tempA = headA;16 ListNode tempB = headB;17 while (tempA != null) {18 ++a;19 tempA = tempA.next;20 }21 while (tempB != null) {22 ++b;23 tempB = tempB.next;24 }25 tempA = headA;26 tempB = headB;27 while (a > b) {28 --a;29 tempA = tempA.next;30 }31 while (b > a) {32 --b;33 tempB = tempB.next;34 }35 while (tempA != null) {36 if (tempA == tempB) {37 return tempA;38 } else {39 tempA = tempA.next;40 tempB = tempB.next;41 }42 }43 return null;44 }45 }
LeetCode Intersection of Two Linked Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。