Leetcode/各大家 -- 160. Intersection of Two Linked Lists

160. Intersection of Two Linked Lists

• Difficulty: Easy

https://leetcode.com/problems/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.

Company: Amazon Microsoft Bloomberg Airbnb

思路： when get to the point length is same, u will get intersection or null by traverse both lists at one time

1, Get the length of the two lists.

2, Align them to the same start point.

3, Move them together until finding the intersection point, or the end null

Complexity: time O(n), space O(1)

关键字： get length of linked list, 

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA),lenB = length(headB);
        while(lenA>lenB){
            headA = headA.next;
            lenA--;
        }
        while(lenA<lenB){
            headB = headB.next;
            lenB--;
        }
        //get the point where rest len of A,B are same
        while(headA!=headB){
            headA = headA.next;
            headB = headB.next;
        }
        return headB;
    }
    public int length(ListNode head){
        int len = 0;
        ListNode node = head;
        while(node!=null){
            len++;
            node = node.next;
        }
        return len;
    }
}