c++ – Find the longest sequence of duplicate numbers in a list

Question:

Assignment: "Create a unidirectional or bidirectional list and find the longest sequence of repeating numbers in the list, keep the repeating value and number of repeats . "

I seem to have created a list, and using the example of arrays, it is clear how to perform the second (interesting) part of the task, but difficulties arose with the implementation of the algorithm for lists. The problem is, I know how to write code to find duplicate values ​​in an array, but I have no idea how to do this for lists.

I would be glad of any help, because I was already a little desperate to find a solution 🙁

#include <iostream>
#include <cstdlib>

using namespace std;

const int size = 8;

struct Node
{
    int Data;
    Node *next; 
    Node *prev; 
};

int main()
{
    Node *Start = NULL;
    Node *End = NULL;
    Node *Current = NULL;

    int i = 0;
    while (i < size)
        {  // Создаем
            Current = new Node;
            Current -> Data = rand() % 5 + 1;
            Current -> prev = NULL;
            Current -> next = NULL;

            // Заполняем
            if (Start == NULL)
                Start = End = Current;
            else
            {
                End -> next = Current;
                Current -> prev = End;
                End = Current;
            }                        
            i++;
        }

    // Выводим
    Current = Start;
    while (Current)
    {
        cout << Current -> Data << endl;
        Current = Current -> next;
    }

    // Удаляем
    Current = End;          
    while (Current)
    {                  
        Node *temp = Current;
        Current = Current -> prev;                        
        delete temp;
    }
    Start = End = NULL;
    return 0;
}

Answer:

Here, I sketched something like this:

int elem_curr = Start->Data;
int elem_prev = Start->Data;
std::size_t length_curr = 1;
std::size_t length_prev = 1;
for(Current = Start; Current != nullptr; Current = Current->next)
{
    if(Current == Start) continue;
    if(elem_curr == Current->Data) length_curr++;
    else
    {
        if(length_curr > length_prev)
        {
            elem_prev = elem_curr;
            length_prev = length_curr;
        }
        elem_curr = Current->Data;
        length_curr = 1;
    }
}

if(length_curr > length_prev)
{
    elem_prev = elem_curr;
    length_prev = length_curr;  
}

std::cout << elem_prev << ' ' << length_prev << std::endl;

And at the beginning of the main function add the line srand(unsigned(time(NULL))); for randomizer

As for the code – optimize a little, I just roughly threw it in, just for the sake of the main idea – looping + searching for a subsequence. For example, the line with continue can be "hushed up" with small additional actions and the check after the cycle for the last one, which is at the end of the list – you can also organize it more beautifully in the cycle. Good luck.

Scroll to Top