亲宝软件园·资讯

展开

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

鹿呦呦 人气:0

一、题目

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

在节点 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+bpB: 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;
}

加载全部内容

相关教程
猜你喜欢
用户评论