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.
代码如下:
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 15 if(headA==null||headB==null)16 return null;17 Map<ListNode,ListNode> map=new <ListNode,ListNode>HashMap();18 19 while(headA!=null||headB!=null)20 {21 22 if(map.containsKey(headA)&&headA!=null)23 return headA;24 else 25 if(!map.containsKey(headA)&&headA!=null)26 {27 map.put(headA,headA);28 headA=headA.next;29 }30 31 32 if(map.containsKey(headB)&&headB!=null)33 return headB;34 else 35 if(!map.containsKey(headB)&&headB!=null)36 {37 map.put(headB,headB);38 headB=headB.next;39 }40 41 }42 43 return null;44 }45 }
原标题:160. Intersection of Two Linked Lists
关键词: