160.相交链表（双指针法）

160. 相交链表（双指针法）

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

一、双指针一起从头走

若相交，链表A： a+c, 链表B : b+c. a+c+b+c = b+c+a+c 。则会在公共处c起点相遇。

若不相交，a +b = b+a 。因此相遇处是NULL

会不会陷入死循环？
不会，因为在无交点的两个链表中，当交换位置后，分别走向对方的最后一个节点，随后next 均为NULL 此时退出循环；
注意 如果while里面搞错，让A or B 不会为NULL 则会陷入死循环

复杂度分析

• 时间复杂度 : O(m+n)。
• 空间复杂度 : O(1)。

#include "stdafx.h"
#include
using namespace std;
struct ListNode
{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){ListNode* a = headA;ListNode* b = headB;while (a != b ){if (a != nullptr){a = a->next;}else{a = headB;} if (b != nullptr){b = b->next;}else{b = headA;}}return a;}
};
int main()
{ListNode headA[7] = { 1, 2, 2, 2, 8, 8, 8 };headA[0].next = &headA[1]; headA[1].next = &headA[2]; headA[2].next = &headA[3];headA[3].next = &headA[4]; headA[4].next = &headA[5]; headA[6].next = &headA[7];ListNode headB[10] = { 3,3,3,3,3,3,3,3,3,3 };headB[0].next = &headB[1]; headB[1].next = &headB[2]; headB[2].next = &headB[3];headB[3].next = &headB[4]; headB[4].next = &headB[5]; headB[6].next = &headB[7];Solution s;auto result = s.getIntersectionNode(headA, headB);return 0;
}

二、双指针有差距起步

思路：
遍历得到两个链表的长度，求长度差diff；
两个指针分别指向两个链表的头结点，让更长的那个链表的指针先走diff步后，两个指针在同时移动，遇到的第一个相同的节点就是他们的公共节点。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{ListNode *CommomNode = nullptr;if(headA != nullptr && headB != nullptr){int countA = 0;int countB = 0;ListNode *pNodeA = headA;ListNode *pNodeB = headB;while(pNodeA != nullptr){countA++;pNodeA = pNodeA->next;}while(pNodeB != nullptr){countB++;pNodeB = pNodeB->next;}//长的链表先走pNodeA = headA;pNodeB = headB;int diff = abs(countA - countB);if(countA > countB){for(int i = 0;i next;}}else if(countA next;}}while(pNodeA!= nullptr && pNodeB != nullptr){if(pNodeA == pNodeB){CommomNode = pNodeA;break;}pNodeA = pNodeA->next;pNodeB = pNodeB->next;}}return CommomNode;
}