首页 > 代码库 > 160. Intersection of Two Linked Lists
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:
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
begin to intersect at node c1.
Solution1: 两次遍历，第一次存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) { Set<ListNode> save=new HashSet<ListNode>(); ListNode remember=headA; while(remember!=null) { save.add(remember); remember=remember.next; } ListNode check=headB; while(check!=null) { if(save.contains(check)) { return check; } check=check.next; } return null; }}
Solution2:
没看到要求是O(1)，补充了一种做法。先比较长短，然后使长的链表缩到小的链表长度。最后遍历，一一对应即可。
/** * 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) { int la=0; ListNode copya=headA; while(copya!=null) { la++; copya=copya.next; } int lb=0; ListNode copyb=headB; while(copyb!=null) { lb++; copyb=copyb.next; } if(la>lb) { while(la!=lb) { headA=headA.next; la--; } } else { while(la!=lb) { headB=headB.next; lb--; } } while(headB!=null&&headA!=null) { if(headA==headB) { return headA; } headA=headA.next; headB=headB.next; } return null;}}
160. Intersection of Two Linked Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。