Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
null.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
解法：两条单链表如果在某个节点相交，那么从这个节点开始，往后的所有节点都是一样的（因为从这个相交节点开始，所有节点的next指针都是一样的）。因此相交节点往后的长度是一样的。因此如果两条链表长度不一样，需要先移动长链表的指针，使得从长度一样的位置处开始一一比较。
/** * 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 *currA = headA, *currB = headB; int diffLen = 0; // 两条链表的长度差 while (currA != NULL && currB != NULL) { currA = currA->next; currB = currB->next; } if (currA != NULL || currB != NULL) { while (currA != NULL) { ++diffLen; currA = currA->next; } while (currB != NULL) { --diffLen; currB = currB->next; } } currA = headA; currB = headB; if (diffLen != 0) { // 存在长度差则先移动到相同长度节点处 while (diffLen-- > 0) currA = currA->next; while (++diffLen < 0) currB = currB->next; } while (currA != NULL && currB != NULL && currA->val != currB->val) { currA = currA->next; currB = currB->next; } return currA; } };
或者先分别算出两条链表长度再比较：
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *currA = headA, *currB = headB; int sizeA = 0, sizeB = 0; while(currA != NULL) { ++sizeA; currA = currA->next; } while(currB != NULL) { ++sizeB; currB = currB->next; } currA = headA; currB = headB; if(sizeA != sizeB) { int diff = sizeA - sizeB; while(diff-- > 0) currA = currA->next; diff = sizeB - sizeA; while(diff-- > 0) currB = currB->next; } while(currA != NULL && currB != NULL && currA->val != currB->val) { currA = currA->next; currB = currB->next; } return currA; } };
[LeetCode]83. Intersection of Two Lists两条单链表的交点
原文：http://www.cnblogs.com/aprilcheny/p/4968190.html