暴力解法尾对齐法双指针法力扣刷题笔记：面试题链表相交

这道题虽然是一道简单题，但是题目设计的非常有趣，我没想到双指针这个方法，这是提交以后在力扣评论区看到的，非常巧妙，逻辑能力真的太重要了。
. 面试题02.07 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。
图示两个链表在节点 c1 开始相交：
题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。
1).暴力解法，暴力解法没什么好说了写两个循环，用A第一个结点对比B所有结点如果没有相等的那么就再遍历下一个；
【暴力解法尾对齐法双指针法力扣刷题笔记：面试题链表相交】/*** 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 *A = headA;ListNode *B = headB;while(A != NULL){while(B != NULL){if(A==B){return A;}B = B->next;}B = headB;A = A->next;}return NULL;}};
缺点时间复杂度高；
2).尾对齐法，题目提升不会出现环，且两个链表相交之后一直重合到空，所以可以先遍历两个链表将它们两个长度求出来，再在长的链表上移动指针直到指针后面的链表长度与短链表相同，再同时移动两个指针，直到它们相等后返回。
/*** 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 *A = headA;ListNode *B = headB;int lenA = 0;int lenB = 0;while(A != NULL){A = A->next;lenA++;}A = headA;while(B != NULL){B = B->next;lenB++;}B = headB;int count = lenA>lenB?(lenA-lenB):(lenB-lenA);if(lenA>lenB){for(int i=0;inext;}}else{for(int i=0;inext;}}while(A != NULL){if(A == B){return A;}A = A->next;B = B->next;}return NULL;}};

文章插图
3).双指针法，这个方法其实理解起来很简单，设两个指针A和B分别指向两个链表头部，指针A跑完链表headA后再从headB头开始跑直到跑完handB，指针B也是这个操作，但是指针B先从headB开始跑。当他们都跑完了以后，他们跑的长度都是headA+headB的长度。
因为同时出发路程一样，所以两个指针同时抵达终点，那这样若是两个链表有交点，交点之后的路程设为c,由于总路程一样，再减去一段相同的路程，那么两个指针是同时到达交点的，只不过相比两个链表不相交时更快遇到。
若两个链表不想交，就是指针A和B同时等于NULL；

/*** 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 *A = headA;ListNode *B = headB;while(A != B){A = A!=NULL?A->next:headB;B = B!=NULL?B->next:headA;}return A;}};

暴力解法尾对齐法双指针法 力扣刷题笔记：面试题 链表相交

暴力解法尾对齐法双指针法力扣刷题笔记：面试题链表相交