-
Notifications
You must be signed in to change notification settings - Fork 0
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
160. Intersection of Two Linked Lists | Linked List
Added sol01_measuring_linked_list_lengths.cpp and updated README for the problem 160
- Loading branch information
1 parent
2b4b3f8
commit 50897ba
Showing
2 changed files
with
84 additions
and
10 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
59 changes: 59 additions & 0 deletions
59
0160_Intersection_of_Two_Linked_Lists/sol01_measuring_linked_list_lengths.cpp
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 1,59 @@ | ||
/* | ||
* Problem 160: Intersection of Two Linked Lists | ||
* https://leetcode.com/problems/intersection-of-two-linked-lists/ | ||
*/ | ||
|
||
// | ||
// Solution 01 - measuring the length of both linked lists | ||
// | ||
|
||
/** | ||
* 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; | ||
ListNode *currB = headB; | ||
|
||
int lengthA = 0; | ||
int lengthB = 0; | ||
|
||
while (currA) { | ||
lengthA ; | ||
currA = currA->next; | ||
} | ||
|
||
while (currB) { | ||
lengthB ; | ||
currB = currB->next; | ||
} | ||
|
||
currA = headA; | ||
currB = headB; | ||
|
||
int diff = lengthA - lengthB; | ||
for (int i = 0; i < std::abs(diff); i) { | ||
if (diff > 0) | ||
currA = currA->next; | ||
else | ||
currB = currB->next; | ||
} | ||
|
||
while (currA != currB) { | ||
if (currA == currB) | ||
break; | ||
|
||
currA = currA->next; | ||
currB = currB->next; | ||
} | ||
|
||
return currA; | ||
} | ||
}; |