-
Notifications
You must be signed in to change notification settings - Fork 765
/
Copy pathIntersection point of 2 linked list
121 lines (97 loc) · 2.63 KB
/
Intersection point of 2 linked list
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// C program to get intersection point of two linked list
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to get the counts of node in a linked list */
int getCount(struct Node* head);
/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int _getIntesectionNode(int d, struct Node* head1, struct Node* head2);
/* function to get the intersection point of two linked
lists head1 and head2 */
int getIntesectionNode(struct Node* head1, struct Node* head2)
{
int c1 = getCount(head1);
int c2 = getCount(head2);
int d;
if (c1 > c2) {
d = c1 - c2;
return _getIntesectionNode(d, head1, head2);
}
else {
d = c2 - c1;
return _getIntesectionNode(d, head2, head1);
}
}
/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int _getIntesectionNode(int d, struct Node* head1, struct Node* head2)
{
int i;
struct Node* current1 = head1;
struct Node* current2 = head2;
for (i = 0; i < d; i++) {
if (current1 == NULL) {
return -1;
}
current1 = current1->next;
}
while (current1 != NULL && current2 != NULL) {
if (current1 == current2)
return current1->data;
current1 = current1->next;
current2 = current2->next;
}
return -1;
}
/* Takes head pointer of the linked list and
returns the count of nodes in the list */
int getCount(struct Node* head)
{
struct Node* current = head;
int count = 0;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
/* IGNORE THE BELOW LINES OF CODE. THESE LINES
ARE JUST TO QUICKLY TEST THE ABOVE FUNCTION */
int main()
{
/*
Create two linked lists
1st 3->6->9->15->30
2nd 10->15->30
15 is the intersection point
*/
struct Node* newNode;
struct Node* head1 = (struct Node*)malloc(sizeof(struct Node));
head1->data = 10;
struct Node* head2 = (struct Node*)malloc(sizeof(struct Node));
head2->data = 3;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 6;
head2->next = newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 9;
head2->next->next = newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 15;
head1->next = newNode;
head2->next->next->next = newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 30;
head1->next->next = newNode;
head1->next->next->next = NULL;
printf("\n The node of intersection is %d \n",
getIntesectionNode(head1, head2));
getchar();
}