编写一个程序，找到两个单链表相交的起始节点。
注意：
如果两个链表没有交点，返回 null.在返回结果后，两个链表仍须保持原有的结构。可假定整个链表结构中没有循环。程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
思路：题目要求用O(n)的时间复杂度：
1.两链表一同遍历，如果pA遍历结束，则pA=headB.
2.两链表一同遍历,如果pB遍历结束，则pB=headA；
3.如果两者有相交的结点，则定会出现pA==pB的情况。
/** * 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) { ListNode* pa = headA; ListNode* pb = headB; if(!pa||!pb) return nullptr; while(true){ if(pa == pb) { return pa; break; } // cout << "pa:" << pa->val << ","; // cout << "pb:" << pb->val << ","; pa = pa->next; pb = pb->next; if(!pa||!pb){ break; } } if(!pa&&!pb) return nullptr; if(!pa) { pa = headB; while(pa){ if(pa == pb){ return pa; } pa = pa->next; pb = pb->next; if(!pb){ pb = headA; } } } else if(!pb){ pb = headA; while(pb){ if(pa == pb){ return pa; } pa = pa->next; pb = pb->next; if(!pa){ pa = headB; } } } return nullptr; } };
转载于:https://www.cnblogs.com/Shinered/p/11421052.html
相关资源：JAVA上百实例源码以及开源项目