Question

How to find the shortest identical consecutive sublist in a linked list with C

Answer 1

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node* next;
} Node;

int* shortest_identical_consecutive_sublst(Node* lst, int* outLen) {
    if (!lst) {
        *outLen = 0;
        return NULL;
    }

    int bestLen = 999999;
    int currentLen = 1;

    Node* bestStartNode = lst;
    Node* currentStartNode = lst;

    Node* prev = lst;
    Node* cur = lst->next;

    while (cur) {
        if (cur->value == prev->value) {
            currentLen++;
        } else {
            if (currentLen < bestLen) {
                bestLen = currentLen;
                bestStartNode = currentStartNode;
            }
            currentStartNode = cur;
            currentLen = 1;
        }
        prev = cur;
        cur = cur->next;
    }

    if (currentLen < bestLen) {
        bestLen = currentLen;
        bestStartNode = currentStartNode;
    }

    int* result = malloc(bestLen * sizeof(int));
    Node* p = bestStartNode;
    for (int i = 0; i < bestLen; i++) {
        result[i] = p->value;
        p = p->next;
    }

    *outLen = bestLen;
    
    return result;
}

/* ============================================================
   MAIN PROGRAM
   ============================================================ */

int main() {
    int arr[] = {3,3,3, 7,7,7,7,7, 2,2, 5,5,5,5, 9,9,9,9,9,9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int outLen;

    Node* lst = NULL;
    Node* tail = NULL;

    for (int i = 0; i < size; i++) {
        Node* node = malloc(sizeof(Node));
        node->value = arr[i];
        node->next = NULL;
        if (!lst) lst = node;
        else tail->next = node;
        tail = node;
    }

    int* resultList = shortest_identical_consecutive_sublst(lst, &outLen);
    printf("List result: ");
    for (int i = 0; i < outLen; i++) printf("%d ", resultList[i]);

    free(resultList);

    return 0;
}



/*
run:
  
List result: 2 2 
  
*/

 

70+ SQL courses for beginners and professionals