一, 题目
编写一个程序, 找到两个单链表相交的起始节点.
如下面的两个链表:
在节点 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;
- }
来源: https://www.cnblogs.com/sunshineliulu/p/12757475.html