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+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;
}
加载全部内容