-
Notifications
You must be signed in to change notification settings - Fork 195
/
Copy pathfind intersection of two Linked Lists using Length.cpp
91 lines (77 loc) · 1.44 KB
/
find intersection of two Linked Lists using Length.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}node;
node *newNode(int data)
{
node *p;
p = (node*)malloc(sizeof(node));
p->data = data; // First node
p->next = NULL;
return p;
}
int find_length(node *start)
{
int cnt = 0;
node *p;
p = start;
while(p!=NULL)
{
cnt++;
p = p->next;
}
return cnt;
}
node *find_intersection(node *p , node *q)
{
node *larger , *smaller;
int m , n , d , cnt;
m = find_length(p); //calculate length
n = find_length(q);
d = m-n; //find difference
if(d < 0) //find absolute value
{
d = d * -1;
}
if(m > n) // find larger length linked list
{
larger = p;
smaller = q;
}
else
{
larger = q;
smaller = p;
}
cnt = 0;
while(cnt < d) // move d nodes in larger linked list
{
larger = larger->next;
cnt++;
}
while(larger != smaller) // then move one step each in both linked lists
{
larger = larger->next;
smaller= smaller->next;
}
return larger; // this is the intersection
}
int main()
{
node *p , *q , *intersection;
p = newNode(1);
p->next = newNode(2);
p->next->next = newNode(3);
p->next->next->next = newNode(4);
intersection = p->next->next->next;
p->next->next->next->next = newNode(5);
p->next->next->next->next->next = newNode(6);
q = newNode(7);
q->next = newNode(8);
q->next->next = intersection;
printf("\n The intersection point is %d",find_intersection(p , q)->data);
return 0;
}