[数据结构与算法]LeetCode160相交链表

class Solution {
public:
	ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
		stack<ListNode*>stA;
		stack<ListNode*>stB;
		if (headA == NULL || headB == NULL) {
			return NULL;
		}
		while (headA) {
			stA.push(headA);
			headA = headA->next;
		}
		while (headB) {
			stB.push(headB);
			headB = headB->next;
		}
		ListNode* result = NULL;
		if (stA.top() == stB.top()) {
			while (!stA.empty() && !stB.empty()) {
				ListNode* A = stA.top();
				stA.pop();
				ListNode* B = stB.top();
				stB.pop();

				if (A == B) {
					result = A;
				}
				else {
					return result;
				}
			}
			return result;
		}
		else {
			return NULL;
		}
		return NULL;
	}
};

解题思路

? 直接杀到链表的尾部，看一下两个链表的尾节点是不是相同，若相同说明必然有相交点，若不相同，可以直接返回null

若最后一个节点相等的话，怎么退回去呢？使用栈，最开始将两个链表分别压入栈中。依次弹出来比较，就可以了。弹得过程中保留上一个节点，若当前节点不相等，说明上一个节点就是相交节点。

代码细节

设置一个变量result保存弹栈元素相同时的值，若弹出来的两个节点相等，就更新result的值，若两个不相等，说明上一个节点就是相交节点，此时返回result即可。还有就是两个链表都只有一个元素，那么一次弹栈操作后，不会在进行弹栈操作，那么需要在循环之外返回result。

代码要考虑到所有出口的情况，不能发生遗漏；另一方面就是所有可能得输入都要考虑到位，不能只解决一直输入情况，可以先解决主要的情况，再将其他情况安插到代码中适当的位置

方法二 链表长度差值法

class Solution {
public:
	ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
		if (headA == NULL || headB == NULL) {
			return NULL;
		}
		int countA = 0;
		int countB = 0;
		int k = 0;
		ListNode* preA = NULL;
		ListNode* preB = NULL;
		ListNode* headA1 = headA;
		ListNode* headB1 = headB;
		ListNode* result = NULL;
		while (headA1) {
			countA++;
			preA = headA1;
			headA1 = headA1->next;
		}
		while (headB1) {
			countB++;
			preB = headB1;
			headB1 = headB1->next;
		}
		if (preA != preB) {
			return NULL;
		}
		if (countA <= countB) {
			k = countB - countA;
			cout << k << endl;
			while (k--) {
				headB = headB->next;
			}
			while (headA) {
				if (headA == headB) {
					return headA;
				}
				headA = headA->next;
				headB = headB->next;
			}

		}
		else {
			k = countA - countB;
			cout << k << endl;
			while (k--) {
				headA = headA->next;
			}
			while (headB) {
				if (headA == headB) {
					return headB;
				}
				headA = headA->next;
				headB = headB->next;
			}
		}
		return NULL;
	}
};

思路

遍历两个链表，获得两者的长度，作差后得到k，将长的链表先走k个元素，再将两个链表逐节点比较

方法三 哈希表

class Solution {
public:
	ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
		set<ListNode*>setA;
		if (headA == NULL || headB == NULL) {
			return NULL;
		}
		while (headA) {
			setA.insert(headA);
			headA = headA->next;
		}
		while (headB) {
			if (setA.find(headB) != setA.end()) {
				return headB;
			}
			else {
				headB = headB->next;
			}
		}
		return NULL;
	}
};

思路

set中不允许有重复的内容，所以先将一个链表中的节点加入进去，再用另一个链表中的元素在set中查找，若能找到，说明有交点，若找不到说明没有交点。