首页 > 代码库 > Intersection of Two Linked Lists
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.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public int getListLength(ListNode N){ int n = 0; ListNode p = N; while(p != null){ n++; p = p.next; } return n; } public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode intersect = null; ListNode pA = headA; ListNode pB = headB; int A = getListLength(headA); int B = getListLength(headB); if(A >= B){ int m = A-B; while(m != 0){ pA = pA.next; m--; } } else{ int m = B-A; while(m != 0){ pB = pB.next; m--; } } while(pA != null){ if(pA == pB){ intersect = pA; break; } else{ pA = pA.next; pB = pB.next; } } return intersect; }}
思路很简单，长的链表先移动指针至和短的链表“同一起跑线”，然后同时移动指针并比较是否相同。
Intersection of Two Linked Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。