【LeetCode

题目描述

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

示例：

Copy

输入：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 个节点。

题目链接：

思路

假设两个链表的长度分别为 lenA 和 lenB，不妨假设 lenA<lenB，两者的长度差 delta=lenB-lenA，则使用两个指针 slow 和 fast 分别从两个链表头开始遍历，fast 先走 delta 步，然后 slow 和 fast 一起走，则 slow 和 fast 相等的节点就是两个链表相交的节点。例如下图

lenA = 5, lenB=6，两者相差 delta=1，slow 指向 A 的链表头，fast 指向 B 的链表头，fast 先走一步（指向 0），然后 slow 和 fast 一起走，则在 8 两个指针相等，表示 8 是相交的节点。

代码如下：

Copy

/** * 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==nullptr || headB==nullptr) return nullptr; int lenA = getLen(headA); int lenB = getLen(headB);语言方法

5634PL2WD5yXFB

j3FpY都丸纱也华

73062011/02/28 12:07:27

int delta = abs(lenA-lenB); ListNode* slow; ListNode* fast; if(lenA>lenB){ fast = headA; slow = headB; }else{ slow = headA; fast = headB; } while(delta>0){ fast = fast->next; delta--; } while(slow!=nullptr && fast!=nullptr){ if(slow==fast) return slow; slow = slow->next; fast = fast->next; } return nullptr; } int getLen(ListNode* head){ int len = 0; while(head!=nullptr){ len++; head = head->next; } return len; }};时间复杂度：O(n)

空间复杂度：O(1)