Find mid of LL without traverse

Explanation

key: use slow and fast pointer Pay attention about the even or odd case !

C version

1
#include <stdio.h>
2
#include <stdlib.h>
3
4
5
struct Node {
6
struct Node* next;
7
int val;
8
};
9
10
11
void addInTail(struct Node **head, int val){
12
struct Node* new = (struct Node*) malloc (sizeof(struct Node));
13
new->val = val;
14
new->next = *head;
15
*head = new;
16
printf("Node: %d\n", new->val);
17
}
18
19
20
int findMidOfLL (struct Node** head){
21
struct Node* slow = *head;
22
struct Node* fast = *head;
23
24
while(fast->next != NULL && fast->next->next != NULL){
25
fast = fast->next->next;
26
slow = slow->next;
27
}
28
29
if(fast->next->next == NULL){ //it's even
30
printf("Event\n");
31
return ((slow->val + (slow->next)->val)/2);
32
}else {
33
printf("Odd\n");
34
return (slow->next)->val;
35
}
36
}
37
Copied!

Test Code

1
int main() {
2
struct Node* head = NULL;
3
4
addInTail(&head, 0);
5
addInTail(&head, 1);
6
addInTail(&head, 3);
7
addInTail(&head, 8);
8
addInTail(&head, -100);
9
addInTail(&head, 49);
10
addInTail(&head, 2);
11
addInTail(&head, -88);
12
13
printf("Mid: %d\n", findMidOfLL(&head));
14
return 0;
15
}
Copied!
Copy link