Skip to content

Latest commit

 

History

History
190 lines (154 loc) · 3.7 KB

160.Intersection-of-Two-Linked-Lists.md

File metadata and controls

190 lines (154 loc) · 3.7 KB

题目地址(160. 相交链表)

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

题目描述

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

前置知识

  • 链表
  • 双指针

解法一: 哈希法

有 A, B 这两条链表, 先遍历其中一个，比如 A 链表, 并将 A 中的所有节点存入哈希表。

遍历 B 链表,检查节点是否在哈希表中, 第一个存在的就是相交节点

  • 伪代码
data=newSet()// 存放A链表的所有节点的地址whileA不为空{哈希表中添加A链表当前节点A指针向后移动}whileB不为空{if如果哈希表中含有B链表当前节点returnBB指针向后移动}returnnull// 两条链表没有相交点
  • 代码支持: JS

JS Code:

letdata=newSet();while(A!==null){data.add(A);A=A.next;}while(B!==null){if(data.has(B))returnB;B=B.next;}returnnull;

复杂度分析

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

解法二：双指针

  • 例如使用 a, b 两个指针分别指向 A, B 这两条链表, 两个指针相同的速度向后移动,
  • 当 a 到达链表的尾部时,重定位到链表 B 的头结点
  • 当 b 到达链表的尾部时,重定位到链表 A 的头结点。
  • a, b 指针相遇的点为相交的起始节点，否则没有相交点

（图 5）

为什么 a, b 指针相遇的点一定是相交的起始节点? 我们证明一下：

  1. 将两条链表按相交的起始节点继续截断，链表 1 为: A + C，链表 2 为: B + C
  2. 当 a 指针将链表 1 遍历完后,重定位到链表 B 的头结点,然后继续遍历直至相交点(a 指针遍历的距离为 A + C + B)
  3. 同理 b 指针遍历的距离为 B + C + A
  • 伪代码
a=headAb=headBwhilea,b指针不相等时{ifa指针为空时a指针重定位到链表B的头结点elsea指针向后移动一位ifb指针为空时b指针重定位到链表A的头结点elseb指针向后移动一位}returna
  • 代码支持: JS, Python, Go, PHP

JS Code:

vargetIntersectionNode=function(headA,headB){leta=headA,b=headB;while(a!=b){a=a===null ? headB : a.next;b=b===null ? headA : b.next;}returna;};

Python Code：

classSolution: defgetIntersectionNode(self, headA: ListNode, headB: ListNode) ->ListNode: a, b=headA, headBwhilea!=b: a=a.nextifaelseheadBb=b.nextifbelseheadAreturna

Go Code:

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcgetIntersectionNode(headA, headB*ListNode) *ListNode { // a=A(a单独部分)+C(a相交部分); b=B(b单独部分)+C(b相交部分)// a+b=b+a=A+C+B+C=B+C+A+Ca:=headAb:=headBfora!=b { ifa==nil { a=headB } else { a=a.Next } ifb==nil { b=headA } else { b=b.Next } } returna }

PHP Code:

/** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val) { $this->val = $val; } * } */class Solution { /** * @param ListNode $headA * @param ListNode $headB * @return ListNode */functiongetIntersectionNode($headA, $headB) { $a = $headA; $b = $headB; while ($a !== $b) { // 注意, 这里要用 !==$a = $a ? $a->next : $headB; $b = $b ? $b->next : $headA; } return$a; } }

复杂度分析

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(1)$
close