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 → b3begin 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.
Special thanks to @stellari for adding this problem and creating all test cases.
------------------------------------------------------------
Solution #1, attach A's end to A's start. solve it as finding the start of cycle in a linked list
/** * 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 == NULL) return NULL; ListNode *end =headA; while (end->next != NULL) { end = end->next; } end->next = headA; ListNode *fast = headB, *slow = headB; while (fast != NULL) { fast = fast->next; slow = slow->next; if (fast != NULL) { fast = fast->next; }else { end->next = NULL; return NULL; } if (slow == fast) break; } if (fast == NULL) { end->next = NULL; return NULL; } fast = headB; while (fast != slow) { slow = slow->next; fast = fast->next; } end->next = NULL; return fast; } };Solution #2
explanation https://oj.leetcode.com/problems/intersection-of-two-linked-lists/solution/
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *endA = NULL, *endB = NULL; ListNode *itrA = headA, *itrB = headB; while (itrA != NULL && itrB != NULL) { if (endA != NULL && endB != NULL && endA != endB) return NULL; if (itrA == itrB) return itrA; if (itrA->next == NULL) { if (endA == NULL) endA = itrA; itrA = headB; }else { itrA = itrA->next; } if (itrB->next == NULL) { if (endB == NULL) endB = itrB; itrB = headA; }else { itrB = itrB->next; } } return NULL; } };
No comments:
Post a Comment