[LeetCode] 160. 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.

<Solution>

這題是要找兩個 linked list 交集開始的那個 node，如果沒有交集，則回傳 NULL

因為有要求 O(1) memory，一樣不能使用 hash map

先看第一種解法，想法如下

• 先從 headA 開始，找到 headA 這條 linked list 的最後一個 node，並將它指向 headB

• 在從 headB 出發，看看是否有形成一個迴圈。如果有，就代表兩條 linked list 是有交集的；如果沒有，就回傳 NULL

• 因為有迴圈了，題目其實就變成找到迴圈的起始點，這時候就可以使用 Floyd's Circle Detection Algorithm 來找就可以了。回傳答案前記得要把迴圈給拿掉

code 如下

	/**
	* 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;
	}
	//>> find the last node of headA
	ListNode *endNode = headA;
	while(endNode->next) {
	endNode= endNode->next;
	}
	endNode->next = headB;
	//>> check is there interstion or not
	ListNode *tmpNode = headB->next;
	bool hasIntersection = false;
	while(tmpNode) {
	if(tmpNode == headB) {
	hasIntersection = true;
	break;
	}
	tmpNode = tmpNode->next;
	}
	if(!hasIntersection) {
	endNode->next = NULL;
	return NULL;
	}
	//>> find start point of loop
	ListNode *slow = headA;
	ListNode *fast = headA;
	while(fast->next && fast->next->next) {
	slow = slow->next;
	fast = fast->next->next;
	if(slow == fast) {
	break;
	}
	}
	slow = headA;
	while(slow != fast) {
	slow = slow->next;
	fast = fast->next;
	}
	endNode->next = NULL;
	return slow;
	}
	};

view raw intersectionOfTwoLinkedLists_1.cpp hosted with ❤ by GitHub

第二種解法十分巧妙且精簡，主要想法是利用走的步數來判斷

用題目來舉例子

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

• 當從 a1 和 b1 各自出發，相重疊的部分走的步數一定一樣，也就是 c1 到 c3  這三步

• 從 a1 走到 c3，共走了 4 步，從 b1 走到 c3 共走了 5 步。這時候， a1 出發的 node 改走到 b1，b1 出發的 node 改走到 a1，這時候，會保證兩者一定在 c1 時相遇，因為都共走了 8 步 (a1-> a2->c1->c2->c3->b1->b2->b3->c1，以及 b1->b2->b3->c1->c2->c3->a1->a2->c1)

• 如果兩者沒有交集，那最後會在都等於 NULL 時相遇(把 NULL 當作一個假想交集點)

code 如下(參考資料)

	/**
	* 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;
	}
	ListNode *nodeA = headA;
	ListNode *nodeB = headB;
	while(nodeA != nodeB) {
	nodeA = nodeA ? nodeA->next : headB;
	nodeB = nodeB ? nodeB->next : headA;
	}
	return nodeA;
	}
	};

view raw intersectionOfTwoLinkedLists_2.cpp hosted with ❤ by GitHub