160. 相交链表
3 min
题目
解法：双指针
思路
双指针同步遍历，通过长度差消除距离差。
该方法正确性在于：若两链表相交，设长度差为d，让长链表指针先移动d步后，两指针剩余遍历距离相同，同步移动时必在交点相遇；若不相交，最终将同时到达null。
- Step 1: 分别计算链表A和B的长度
- Step 2: 将较长链表的头指针向后移动长度差步
- Step 3: 双指针同步遍历，直到相遇或同时到达末尾
复杂度
- 时间复杂度: ，其中m、n为两链表长度，主要耗时在两次长度计算和同步遍历
- 空间复杂度: ，仅使用固定数量的指针变量
代码
/**
* 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) {
int lenA = 0;
int lenB = 0;
for (ListNode* p = headA; p != NULL; p = p->next) {
lenA++;
}
for (ListNode* p = headB; p != NULL; p = p->next) {
lenB++;
}
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) {
headA = headA->next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
/**
* 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) {
int lenA = 0;
int lenB = 0;
for (ListNode* p = headA; p != NULL; p = p->next) {
lenA++;
}
for (ListNode* p = headB; p != NULL; p = p->next) {
lenB++;
}
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) {
headA = headA->next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
headB = headB->next;
}
}
while (headA != headB) {
headA = headA->next;
headB = headB->next;
}
return headA;
}
};