leetcode 好题 00 -- Intersection of Two Linked Lists
05 June 2018

leetcode 160. 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.

两条链表有重叠部分,找出重叠的位置

思路:O(n^2) 解法

foreach list1 as n1
    foreach list2 as n2
        if n1 == n2
            return n1

下面是两种好的解法
解法1:
如果 list1 的长度和 list2 的长度是一样长的,类似下面这种,那么我们逐个比较就好了

a1 → a2
       ↘
          c1 → c2 → c3
       ↗
b1 → b2

while (list1 && list2) {
    if (list1->val == list2->val) {
        return list1;
    }
    list1 = list1->next;
    list2 = list2->next;
}

如果 list1 的长度和 list2 的长度不一样长的,思路把长度大的那块去掉,变成一样长的两个链表

list1 = a1 → c1 → c2 → c3
list2 = a1 → c1 → c2

list1 = a1 → a2 → c1 → c2 → c3
list2 =           c1 → c2 → c3

while (len1 != len2 && list1 && list2) {
    if (list1 == list2) {
        return list1;
    }

    if (len1 > len2) {        // 如果是 list1 长一些
        list1 = list1->next;
        len1--;
    }

    if (len2 > len1) {        // 如果是 list2 长一些
        list2 = list2->next;
        len2--;
    }
}

解法2:

newlist1 = list1 + list2;
newlist2 = list2 + list1;
while (newlist1 && newlist2) {
    if (newlist1 == newlist2) {
        return newlist1;
    }

    newlist1 = newlist1->next;
    newlist2 = newlist2->next;
}