巴彦淖尔市网站制作内蒙古最新消息

前言

题目： 160. 相交链表
文档： 代码随想录——链表相交
编程语言： C++
解题状态： 没思路…

思路

依旧是双指针法，很巧妙的方法，有点想不出来。

代码

先将两个链表末端对齐，然后两个指针齐头并进，容易判断出是否相交。

/*** 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) {ListNode* curA = headA;ListNode* curB = headB;int lenA = 0;int lenB = 0;while (curA) {++lenA;curA = curA -> next;}while (curB) {++lenB;curB = curB -> next;}curA = headA;curB = headB;if (lenB > lenA) {swap(lenA, lenB);swap(curA, curB);}int gap = lenA - lenB;while (gap--) {curA = curA -> next;}while (curA) {if (curA == curB) {return curA;}curA = curA -> next;curB = curB -> next;}return NULL;}
};

• 时间复杂度： $O(m+n)$
• 空间复杂度： $O(1)$