Intersection of Two Linked Lists LeetCode solution in C++

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 * int val;
5
 * ListNode *next;
6
 * ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
 public:
11
  // function to get length of linked list
12
  int getLength(ListNode *head) {
13
    // initial length 0
14
    int l = 0;
15

16
    while (head != NULL) {
17
      l++;
18
      head = head->next;
19
    }
20
    return l;
21
  }
22

23
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
24
    // ptr1 & ptr2 will move to check nodes are intersecting or not
25
    // ptr1 will point to the list which have higher length, higher elements
26
    // (big list) ptr2 will point to small list
27
    ListNode *ptr1, *ptr2;
28

29
    // fetching length of both the list,as we want a node that both ptr points
30
    // simultaneously so if both list have same length of nodes, they travel
31
    // with same speed, they intersect if diff legths, it'll be difficult for us
32
    // to catch so by substracting list with higher length with lower length we
33
    // get same level of length, from which both ptr start travaeling, they may
34
    // get intersect
35
    int length1 = getLength(headA);
36
    int length2 = getLength(headB);
37

38
    int diff = 0;
39

40
    // ptr1 points to longer list
41
    if (length1 > length2) {
42
      diff = length1 - length2;
43
      ptr1 = headA;
44
      ptr2 = headB;
45

46
    } else {
47
      diff = length2 - length1;
48
      ptr1 = headB;
49
      ptr2 = headA;
50
    }
51

52
    // till diff is zero and we reach our desired posn
53
    while (diff) {
54
      // incrementing ptr1 so that it can be at a place where both list have
55
      // same length
56

57
      ptr1 = ptr1->next;
58

59
      if (ptr1 == NULL) {
60
        return NULL;
61
      }
62

63
      diff--;
64
    }
65

66
    // traverse both pointers together, till any of them gets null
67
    while ((ptr1 != NULL) && (ptr2 != NULL)) {
68
      // at any point, both point to same node return it
69
      if (ptr1 == ptr2) {
70
        return ptr1;
71
      }
72

73
      // increment both pointers, till they both be NULL
74
      ptr1 = ptr1->next;
75
      ptr2 = ptr2->next;
76
    }
77

78
    // if not found any intersaction, return null
79
    return NULL;
80
  }
81
};