题解 | #两个链表的第一个公共结点#

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
#include <cmath>
#include <iterator>
#include <stack>
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        // 常规思路：反转列表后，依次遍历进栈，若不相同循环结束，出栈组成新节点
		// ListNode *res = new ListNode(0);
		// ListNode *temp = res;
		// // 特殊情况已考虑
		// // if (pHead1 == nullptr || pHead2 == nullptr) {
		// // 	return res->next;
		// // }
		// // if (pHead1 == pHead2) {
		// // 	return pHead1;
		// // }
		// stack<int> st1;
		// stack<int> st2;
		// stack<int> st3;

		// while (pHead1) {
		// 	st1.push(pHead1->val);
		// 	pHead1 = pHead1->next;
		// }
		// while (pHead2) {
		// 	st2.push(pHead2->val);
		// 	pHead2 = pHead2->next;
		// }
		// // 调试栈
		// // while (!st2.empty()) {
		// // 	cout << st2.top() << " ";
		// // 	st2.pop();
		// // }
		// // 调试断点
		// // return;

		// while (!st1.empty() && !st2.empty() && st1.top() == st2.top()) {
		// 	st3.push(st1.top());
		// 	st1.pop(), st2.pop();
		// 	if (st1.empty() || st2.empty()) break;
		// }
		// while (!st3.empty()) {
		// 	temp->next = new ListNode(st3.top());
		// 	temp = temp->next;
		// 	st3.pop();
		// }
		// return res->next;

		// 两个链表拼接，从头开始切，剩下的链表相等时结束
		ListNode *left = pHead1;
		ListNode *right = pHead2;	
		while (left != right) {
			left = left ? left->next : pHead2;
			right = right ? right->next : pHead1;
		}
		return left;
    }
};