LeetCode(LinkedList)Intersection of Two LinkedList

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.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

思路：常规思路，最笨的办法就是借助容器来存储每个链表的每个节点，然后两层嵌套for循环去判断所有情况即可，此算法容易理解，且运行正确，就是最后一个测试用例超时了，因为时间复杂度和空间复杂度均较高，但是第二次运行通过了，: )。但还需要优化

代码如下：

/**
 * 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) {
        if(headA==null || headB==null){
            return null;
        }
        ArrayList<ListNode> listA=new ArrayList<>();
        ArrayList<ListNode> listB=new ArrayList<>();
        ListNode tempA=headA;
        while(tempA!=null){
            listA.add(tempA);
            tempA=tempA.next;
        }
        ListNode tempB=headB;
        while(tempB!=null){
            listB.add(tempB);
            tempB=tempB.next;
        }
        
        int lenA=listA.size();
        int lenB=listB.size();
        ListNode res=null;
        for(int i=0;i<lenA;i++){
            for(int j=0;j<lenB;j++){
                if(listA.get(i)==listB.get(j)){
                    res=listA.get(i);
                    return res;
                }
            }
        }
        return res;
    }
}