欢迎访问LeetCode题解合集
题目描述
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
[HTML_REMOVED]
[HTML_REMOVED]
在节点 c1 开始相交。
示例 1：
[HTML_REMOVED]
[HTML_REMOVED]
输入：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：
[HTML_REMOVED]
[HTML_REMOVED]
输入：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：
[HTML_REMOVED]
[HTML_REMOVED]
输入：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) 内存。
题解：
法一：
想办法让两个链表上的指针 齐头并进 ，相等的时候就是第一个相交节点。
具体来说：
- 分别统计两个链表的长度，并记录最后一个节点，如果最后一个节点不相等，那么两个链表不相交；否则记长度差值为
gap - 让长的链表从头开始先走
gap步，然后两个指针齐头并进，第一次相等的地方就是相交的节点。
时间复杂度：$O(m + n)$
额外空间复杂度：$O(1)$
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if ( !headA || !headB ) return NULL;
ListNode *p1 = headA, *p2 = headB;
int n = 0;
while ( p1->next ) {
p1 = p1->next;
++n;
}
while ( p2->next ) {
p2 = p2->next;
--n;
}
if( p1 != p2 ) return NULL;
p1 = headA, p2 = headB;
if( n < 0 ) n = -n, swap( p1, p2 );
while ( n-- ) p1 = p1->next;
while ( p1 != p2 ) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
};
/*
时间：60ms，击败：33.09%
内存：14.2MB，击败：80.10%
*/
法二：
假设相交部分长度为 c ，两个链表距离第一个相交节点的长度分别为 a 和 b，可以让两个指针分别从头节点开始，若遍历到空节点，则让其指向另一个链表的头节点，最终两个指针相等时就是相交的第一个节点。
其核心思想与 方法一 基本一样：方法一是让长度较长的链表指针先走 gap 步，而 方法二 是让长度较短的链表指针先走 gap 步。
设 p 指向长度较长的链表，其长度为 a ，q 指向长度较短的链表，其长度为 b 。当 p 走 a + c 步时，q 从头节点到尾节点共走 b + c 步，剩下的 a - b 步是其在长度较长的链表上走的。此时 p 距离尾节点还剩 b + c 步，q 节点距离尾节点还剩 a + c - a + b = b + c 步，两个指针一起向前移动，相等时就是第一个相交的节点。
时间复杂度：$O(n + m)$
额外空间复杂度：$O(1)$
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if ( !headA || !headB ) return NULL;
ListNode *p = headA, *q = headB;
while ( p != q ) {
if( p ) p = p->next;
else p = headB;
if( q ) q = q->next;
else q = headA;
}
return p;
}
};
/*
时间：52ms，击败：67.20%
内存：14.2MB，击败：80.10%
*/
