LeetCode160 相交链表

前言

题目：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)$