leetcode [#160]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Write a program to find the node at which the intersection of two singly linked lists begins.

Example:
the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3

begin to intersect at node c1.

---

解决方案

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */
 * 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) {
        ListNode result = null;
        if(headA == null || headB == null) return result;

        ListNode h1 = new ListNode(0);
        ListNode h2 = new ListNode(0);
        h1.next = headA;
        h2.next = headB;

        LinkedHashSet<ListNode> set = new LinkedHashSet<>();
        while(h1 != null){
            set.add(h1);
            h1 = h1.next;
        }

        while(h2 != null){
            if(set.add(h2) == false){
                result = h2;
                break;
            }
            h2 = h2.next;
        }
        return result;
    }
}

---

注意事项

1. 遍历其中任意一个链表，将所有元素都加入一个LinkedHashSet，再遍历另一个链表，也将每个元素依次加入该set，当add方法返回false时，说明该节点已经存在，也就是两个链表指向的公共节点，返回该节点即可。
2. 以下方法理解起来更容易但并不可行，o(n^2)的复杂度会导致超时：

   public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode result = null;
       if(headA == null || headB == null) return result;
   
       ListNode h1 = new ListNode(0);
       ListNode h2 = new ListNode(0);
       h1.next = headA;
       h2.next = headB;
   
       while (h1 != null){
           boolean intersection = false;
           while(h2 != null){
               if(h1.next == h2.next){
                   intersection = true;
                   result = h1.next;
                   break;
               }
               h2 = h2.next;
           }
           if(intersection){
               break;
           }
           h2 = new ListNode(0);
           h2.next = headB;
           h1 = h1.next;
       }
   
       return result;
   }