LeetCode#160-Intersection of Two Linked Lists-相交链表

一、题目

编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：

在节点 c1 开始相交。

示例 1:

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2:

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3:

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由
于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

二、题解

• 题解1：哈希表

遍历链表 A 并将每个节点的地址/引用存储在哈希表中。
然后检查链表 B 中的每一个节点是否在哈希表中。若在，则为相交结点。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 func getIntersectionNode(headA, headB *ListNode) *ListNode {
    var s [] *ListNode

    for headA != nil {
        s = append(s, headA)
        headA = headA.Next
    }
    for headB != nil {
        for _,v := range(s) {
            if v == headB {
                return headB
            }
        }
        headB = headB.Next
    }
    return nil
}

• 题解2：链表拼接法

当链表 A 走到尾部的 null 时，转到链表 B 的头节点继续走；
当链表 B 走到尾部的 null 时，转到链表 A 的头节点继续走；
若两链表相交，则 A 和 B 一定相遇。

如上图：初始化 pA = headA, pB = headB，开始遍历。
pA会先到达链表尾，当pA到达末尾时，重置pA为headB；同样的，当pB到达末尾时，重置pB为headA。当pA与pB相遇时，必然就是两个链表的交点。

为什么要这样处理？因为对 pA 而言，走过的路程为 a+c+b，对 pB 而言，为 b+c+a，显然 a+c+b = b+c+a，这就是该算法的核心原理。

即使两个链表没有相交点，仍然可以统一处理，因为这种情况意味着相交点就是 null，也就是上图中的公共部分c没有了，从而递推式变成了 pA: a+b，pB: b+a，同样是成立的。

时间复杂度：O(m+n)，空间复杂度：O(1)。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if (headA == nil || headB == nil) {
        return nil
    }
    pA, pB := headA, headB
    for pA != pB {
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }
        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }
    return pA
}

• 题解3：消除链表长度差

两个单链表，有公共结点，则必然尾部公用；

分别找出链表 1 和链表 2 的长度，长的链表减去短的链表得出一个 n 值；

长的链表先走 n 步，两个链表再同时移动，则两个链表相交点就是第一个公共结点。

时间复杂度：O(n)，空间复杂度：O(1)。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    lenA := getLen(headA)
    lenB := getLen(headB)

    //计算链表长度差 n，长的先移动 n 步
    if (lenA > lenB) {// 链表A比链表B长，A先移动
        for i := 0; i < lenA - lenB; i++ {
            headA = headA.Next
        }
    } else {// 链表B比链表A长，B先移动
        for i := 0; i < lenB - lenA; i++ {
            headB = headB.Next
        }
    }

    for headA != nil {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil;
}

//获取链表长度
func getLen(head *ListNode) int {
    var len int
    for head != nil {
        len++
        head = head.Next
    }
    return len
}

后记

这道题也是面试题中经常遇到的“两个链表的第一个公共节点”。虽然难度是“简单”，但对我来说一点也不简单。看评论和题解涨了很多姿势。

而且，一开始用的是 PHP，可怎么都通不过，不得不用 Go 重写了一遍，倒是很快通过了。

附上 PHP 版本：

• 题解1 PHP版本

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val) {
        $this->val = $val;
    }
}

/**
 * @param ListNode $headA
 * @param ListNode $headB
 * @return ListNode
 */
function getIntersectionNode($headA, $headB) {
    $hashMap = [];
    while ($headA) {
        $hashMap[] = $headA;
        $headA = $headA->next;
    }
    while ($headB) {
        if (in_array($headB, $hashMap)) {
            return $headB;
        }
        $headB = $headB->next;
    }
    return null;
}

• 题解2 PHP版本

function getIntersectionNode($headA, $headB) {
    if ($headA == null || $headB == null) {
        return null;
    }

    $pA = $headA;
    $pB = $headB;
    while ($pA != $pB) {
        $pA = $pA == null ? $headB : $pA->next;
        $pB = $pB == null ? $headA : $pB->next;
    }
    return $pA;
}

• 题解3 PHP版本

function getIntersectionNode($headA, $headB) {
    $lenA = getListLength($headA);
    $lenB = getListLength($headB);

    $diffLen = $lenA > $lenB ? $lenA - $lenB : $lenB - $lenA;
    $headLong = $lenA > $lenB ? $headA : $headB;
    $headShort = $lenA > $lenB ? $headB : $headA;

    //先在长链表上走几步，再同时在两个链表上遍历
    for ($i = 0; $i < $diffLen; $i++) {
        $headLong = $headLong->next;
    }
    while ($headLong != $headShort) {
        $headLong = $headLong->next;
        $headShort = $headShort->next;
    }
    return $headLong;
}

/**
 * 获取链表的长度
 */
function getListLength($head)
{
    $length = 0;
    $current = $head;
    while ($current != null) {
        $length++;
        $current = $current->next;
    }
    return $length;
}