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.假设两个链表有合并的情况，那么合并部分的长度一定是一样的，在合并之前长度会有所不同，所以先求出长度，然后把长的链表向前走，让他们“在同一起跑线”，然后依次比较。
/** * 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) { if (!headA || !headB) return NULL; int lenA = 0, lenB = 0; ListNode *nodeA, *nodeB; for (nodeA = headA; nodeA; nodeA = nodeA->next, ++lenA); for (nodeB = headB; nodeB; nodeB = nodeB->next, ++lenB); if (lenB > lenA) { for (int i = 0; i < lenB - lenA; ++i, headB = headB->next); } else { for (int i = 0; i < lenA - lenB; ++i, headA = headA->next); } if (headA == headB) return headA; while (headA && headB) { headA = headA->next; headB = headB->next; if (headA == headB) return headA; } return NULL; } };
【LeetCode】160. Intersection of Two Linked Lists
原文：http://www.cnblogs.com/jdneo/p/4797408.html