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中查找,若能找到,说明有交点,若找不到说明没有交点。