160. Intersection of Two Linked Lists | Linked List

Added sol01_measuring_linked_list_lengths.cpp and updated README for the problem 160
milan-r-shah · Oct 4, 2020 · 50897ba · 50897ba
1 parent 2b4b3f8
commit 50897ba
Show file tree

Hide file tree

Showing 2 changed files with 84 additions and 10 deletions.
diff --git a/0160_Intersection_of_Two_Linked_Lists/README.md b/0160_Intersection_of_Two_Linked_Lists/README.md
@@ -1,5 1,5 @@
-#### LeetCode 
-### Problem 160: Intersection of Two Linked Lists
 ### LeetCode 
 ## Problem 160: Intersection of Two Linked Lists
 
 https://leetcode.com/problems/intersection-of-two-linked-lists/
 
@@ -11,45 11,60 @@ Write a program to find the node at which the intersection of two singly linked
 
 For example, the following two linked lists:
 
 <!-- ![example](README_data/example.png "Example") -->
 
-![example](README_data/example.png "Example")
 <img src="README_data/example.png" alt="example" width="800">
 
 begin to intersect at node c1.
 
 <br>
 
 #### Example 1:
 
-![example_1](README_data/example_1.png "Example_1")
 <!-- ![example_1](README_data/example_1.png "Example_1") -->
 
 <img src="README_data/example_1.png" alt="example_1" width="800">
 
 <pre>
 <b>Input:</b> intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
 <b>Output:</b> Reference of the node with value = 8
-<b>Input Explanation:</b> The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
 <b>Input Explanation:</b> The intersected node's value is 8 (note that this must not be 0 if the two
  lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head
  of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected 
  node in A; There are 3 nodes before the intersected node in B.
 </pre>
 
 <br>
 
 #### Example 2:
 
-![example_2](README_data/example_2.png "Example_2")
 <!-- ![example_2](README_data/example_2.png "Example_2") -->
 
 <img src="README_data/example_2.png" alt="example_2" width="800">
 
 <pre>
 <b>Input:</b> intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
 <b>Output:</b> Reference of the node with value = 2
-<b>Input Explanation:</b> The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
 <b>Input Explanation:</b> The intersected node's value is 2 (note that this must not be 0 if the two 
  lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head 
  of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; 
  There are 1 node before the intersected node in B.
 </pre>
 
 <br>
 
 #### Example 3:
 
-![example_3](README_data/example_3.png "Example_3")
 <!-- ![example_3](README_data/example_3.png "Example_3") -->
 
 <img src="README_data/example_3.png" alt="example_3" width="800">
 
 <pre>
 <b>Input:</b> intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
 <b>Output:</b> null
-<b>Input Explanation:</b> From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
 <b>Input Explanation:</b> From the head of A, it reads as [2,6,4]. From the head of B, it reads 
  as [1,5]. Since the two lists do not intersect, intersectVal must be 0, 
  while skipA and skipB can be arbitrary values.
 <b>Explanation:</b> The two lists do not intersect, so return null.
 </pre>
 
@@ -72,5 87,5 @@ begin to intersect at node c1.
 ---
 
 **Useful Links:**
-1. Find intersection of two linked lists (by measuring linked list length) - Vivekanand Khyade -- [video](https://youtu.be/_7byKXAhxyM)
 1. Find intersection of two linked lists (by measuring length of both linked lists) - Vivekanand Khyade -- [video](https://youtu.be/_7byKXAhxyM)
 2. Find merge point of two linked list - mycodeschool -- [video](https://youtu.be/gE0GopCq378)
diff --git a/0160_Intersection_of_Two_Linked_Lists/sol01_measuring_linked_list_lengths.cpp b/0160_Intersection_of_Two_Linked_Lists/sol01_measuring_linked_list_lengths.cpp
@@ -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;
  }
 };