LeetCode 160. 相交链表

Scroll Down

LeetCode 160. 相交链表

题目:

编写一个程序,找到两个单链表相交的起始节点。

哈希表法

遍历链表L1,将所有的结点存到HashSet中,然后遍历L2,判断是否在L1中,如果存在,就认为是有相交结点,否则认为没有相交

 public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        Set<ListNode> nodes = new HashSet<>();
        while (headA != null) {
            nodes.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            //判断是否有相交结点
            if (nodes.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
     //没有的话返回null
        return null;
    }

双指针法

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tempA = headA;
        ListNode tempB = headB;
        while(tempA != tempB){
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next;
        }
        return tempA;
	}

首先这里先循环遍历,如果链表A走到了终点,则将tempA指向链表B的头结点,如果链表B走到了终点,则将tempB指向链表A的头结点.假如A链表的长度是4,B链表的长度是6.
image-20200329204314030

当链表A走到终点时,链表B走到第4个节点,此时将链表A移到到链表B的头结点

image-20200329204910246

此时继续循环,B走到终点时,将B移到链表A的头结点

image-20200329204936013

继续遍历往下走,因为循环条件是两者不相等的时候都要继续遍历,如果两者不想交,最终都等于null就会返回null,此时B移动到A链表头

image-20200329205106962

此时继续走两步,两者在相交点相等
image-20200329205140441

原理是因为链表A = a+c,链表B=b+c,然后如果相交的话,a+c+b = b+c+a;

image-20200329210240864