输入两个链表,找出它们的第一个公共结点。
一定是Y型的结构
从末尾开始遍历,如果有不同的,那么前一个节点就是第一个公共节点。
思路,把节点放到栈结构里面,然后进行比较节点。
#include <iostream> #include <string> #include<vector> #include<algorithm> #include <stack> using namespace std; struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; class Solution { public: ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) { if (!pHead1 || !pHead2) return NULL; stack<ListNode *>p1; stack<ListNode *>p2; ListNode* node = NULL; while (pHead1){ p1.push(pHead1); pHead1 = pHead1->next; } while (pHead2){ p2.push(pHead2); pHead2 = pHead2->next; } while ((p1.size()>0 && p2.size()>0) && p1.top() == p2.top()){ cout << p1.top()->val <<" "<< p2.top()->val << endl; node = p1.top(); p1.pop(); p2.pop(); } return node; } }; int main(){ Solution s; ListNode *pHead1 = new ListNode(1); pHead1->next = new ListNode (2); pHead1->next->next = new ListNode(3); ListNode *pHead2 = new ListNode(1); pHead2->next = pHead1->next->next; ListNode * node = s.FindFirstCommonNode(pHead1, pHead2); if (node) cout << node->val << endl; }
View Code
原文链接: https://www.cnblogs.com/yuguangyuan/p/5945742.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/398037
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!