Find mid of LL without traverse

Search…

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!

DS with C - Previous

Implement Queue with LL

Next - DS with C

Delete a Node from LL

Last modified 5mo ago

Copy link

Contents

Explanation

C version