本文主要是介绍leetcode No160. Intersection of Two Linked Lists，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Question:
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2↘c1 → c2 → c3↗ B: b1 → b2 → b3
begin to intersect at node c1.
Algorithm:
算法1：分别把两个链表的结点放入两个栈里，这样两个链表的尾结点就位于两个栈的栈顶，接下来比较元素是否相同
算法2：首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，这样第二次遍历的时候，在较长的链表上先走，接着短的再走，这样找到的第一个相同的结点就是它们的第一个公共结点
Accepted Code：
算法1：
/*** 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) {if(headA==NULL || headB==NULL)return NULL;stack<ListNode*> s1;stack<ListNode*> s2;ListNode *p1=headA;ListNode *p2=headB;while(p1){s1.push(p1);p1=p1->next;}while(p2){s2.push(p2);p2=p2->next;}ListNode *res=NULL;while((!s1.empty() && !s2.empty()) && s1.top()==s2.top()){res=s1.top();s1.pop();s2.pop();}return res;}
}; 算法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) {int len1=0;int len2=0;ListNode *p1=headA;ListNode *p2=headB;while(p1){p1=p1->next;len1++;}while(p2){p2=p2->next;len2++;}int lendiff=0;ListNode *pHeadLong=NULL;ListNode *pHeadShort=NULL;if(len1>len2){pHeadLong=headA;pHeadShort=headB;lendiff=len1-len2;}else{pHeadLong=headB;pHeadShort=headA;lendiff=len2-len1;}for(int i=0;i<lendiff;i++)pHeadLong=pHeadLong->next;while(pHeadLong!=NULL && pHeadShort!=NULL && pHeadShort!=pHeadLong){pHeadLong=pHeadLong->next;pHeadShort=pHeadShort->next;}ListNode *res=pHeadLong;return res;}
};看到某大神解法，A、B同时遍历，记为p1,、p2，当p1遍历到A的尾结点时，再从B的头结点开始遍历。p2遍历到B的尾结点时，再从A的头结点开始遍历。
证明如下：绿色为p1路线，红色为p2路线，它们最后肯定会在交叉处相遇，算法的缺陷就是不相交的时候要遍历2遍。
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* p1=headA;ListNode* p2=headB;while(p1!=p2){if(p1!=NULL)p1=p1->next;elsep1=headB;if(p2!=NULL)p2=p2->next;elsep2=headA;}return p1;}
};这篇关于leetcode No160. Intersection of Two Linked Lists的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
