首页 > 代码库 > [Leetcode]Intersection of Two Linked Lists

[Leetcode]Intersection of Two Linked Lists

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:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.
题意是求两个链表的交集。这里考虑到链表的性质,如果从某一个节点开始,两个链表元素都指向同一个元素的话,那么从这个元素开始,后边都是交集。

根据上述性质,如果两个链表等长,那么只要两个链表指针匀速向后移动,当两个指针第一次相等时就找到了交集开始的元素。

如果两个链表不等长,就去掉较长链表多出来的部分,使链表等长,然后再进行上述步骤。(因为交集不可能从多出来的部分开始)

如果两个链表最后一个元素指针也不同,则证明两个链表没有交集。所以,我在求链表长度的方法里加了一个返回值,用pair类型同时返回了链表长度和链表最后一个元素指针,如果最后一个元素指针都不同,就直接返回NULL,不再进行下面的步骤了。

中间还用到一些指针引用神马的,自觉写的还是比较优雅的,请大家多多提出意见~~~

class Solution {
public:
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		if (NULL == headA || NULL == headB) return NULL;
		ListNode *tmpA = headA,*tmpB = headB;
		pair<int, ListNode *> pairA = calLength(headA);
		pair<int, ListNode *> pairB = calLength(headB);
		int lengthA = pairA.first;
		int lengthB = pairB.first;
		ListNode *lastA = pairA.second;
		ListNode *lastB = pairB.second;
		if (lastA != lastB) return NULL;
		ListNode *&longList = lengthA >= lengthB ? tmpA : tmpB;
		ListNode *&shortList = lengthA >= lengthB ? tmpB : tmpA;
		for (int i = 0; i < abs(lengthA - lengthB); i++){
			longList = longList->next;
		}
		while (NULL != longList && NULL != shortList){
			if (longList == shortList){
				return longList;
			}
			longList = longList->next;
			shortList = shortList->next;
		}
		return NULL;
	}
	pair<int,ListNode *> calLength(ListNode *root){
		ListNode *tmp = root;
		int length = 1;
		while (tmp->next != NULL){
			length++;
			tmp = tmp->next;
		}
		return pair<int, ListNode *>(length,tmp);
	}
};




[Leetcode]Intersection of Two Linked Lists