160. Intersection of Two Linked Lists - jiejackyzhang/leetcode-note GitHub Wiki

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.

##Approach 1: different length of two lists 获取两个lists的长度差，然后让长的先走，在同一长度的地方再依次判断是否相同。 缺点是两个lists都遍历了两遍。

/**
 * 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) {
        int lenA = 0, lenB = 0;
        ListNode p = headA;
        while(p != null) {
            p = p.next;
            lenA++;
        }
        p = headB;
        while(p != null) {
            p = p.next;
            lenB++;
        }
        ListNode pLong = lenA >= lenB ? headA : headB;
        ListNode pShort = lenA < lenB ? headA : headB;
        int diff = Math.abs(lenA - lenB);
        while(diff != 0) {
            pLong = pLong.next;
            diff--;
        }
        while(pLong != null && pShort != null) {
            if(pLong == pShort) {
                return pLong;
            }
            pLong = pLong.next;
            pShort = pShort.next;
        }
        return null;
    }
}

##Approach 2: hash set 采用hash set来存list A的listNode，然后遍历list B来判断是否有相同的node。 优点是两个list各遍历一遍，但是hash set本身比较费时间，而且空间占用了O(n)。

/**
 * 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;
        Set<ListNode> set = new HashSet<ListNode>();
        while(headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while(!set.contains(headB) && headB != null) {
            headB = headB.next;
        }
        return headB;
    }
}

##Approach 3: without diff len 这是一种非常巧妙的方法。 若两个lists长度相同，则第一次iteration就可判断是否有intersection。 若两个lists长度不同，则第二次iteration时将指针指向另一个list的head，则两个指针在第二次iteration时到list尾部的长度相同，转化为了长度相同时的情况。 这个方法也会两次遍历两个lists，但是不需要计算它们的长度差。

/**
 * 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;
        ListNode a = headA;
        ListNode b = headB;
        while(a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a;
    }
}
⚠️ **GitHub.com Fallback** ⚠️