你的位置:首页 > Java教程

[Java教程]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.

 

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 }