Question

Given a doubly linked list in c++, how do I create a function that returns the pointer to first node in the given pattern, For example, given mainList (a -> b -> c -> d) and sublist  (b -> c), our function should return a Node pointer that points to first node of the sublist in the mainList. If the pattern doesn't exist in the mainList, we should return a nullptr, there are multiple of the same sublist in the mainList, we should return the very first instance where pattern is seen. The implementation must use doubly linked list, turning the patterns into strings and using find isn't allowed.

struct Node {

char value;

Node* next;

Node* prev;

}

Node* findList(Node* subList, Node* mainList) {

// need to do this

}

void printList(Node* node)
{
    while (node != nullptr)
    {
        printf("%c ", node->value);
        node = node->next;
    }
}

Node *newNode(char key)
{
    Node *temp = new Node;
    temp->value= key;
    temp->next = nullptr;
    return temp;
}

int main() {
    // this is the sublist
    Nucleotide *a = newNode('T');
    a->next = newNode('G');
    a->next->next = newNode('T');
    a->next->next->next = nullptr;

    // this is the main list
    Node *b = newNode('A');
    b->prev = nullptr;
    b->next = newNode('A');
    b->next->prev = b;
    b->next->next = newNode('C');
    b->next->next->prev = b->next;
    b->next->next->next = newNode('T');
    b->next->next->next->prev = b->next->next;
    b->next->next->next->next = newNode('G');
    b->next->next->next->next->prev = b->next->next->next;
    b->next->next->next->next->next = newNode('A');
    b->next->next->next->next->next->prev = b->next->next->next->next;
    b->next->next->next->next->next->next = nullptr;
    printList(a);
    cout << endl;
    printList(b);
    cout << endl;
    Node *c = findList(a, b);
    cout << c->value << endl;

    return 0;
}

Answer 1

So In the above problem statement we are given two doubly linked lists mainlist and dublist we are to check whether sublist is present in mainlist or not. if present then return Node pointer that points to first node of the sublist in the mainList else simply return NULL.

we stored mainlist and sublist in two string vaiable main and sub respectively. now our problem is converted to find first occurence of a string in other(sub in main).

we stored the first occurence in a variable named count ,now it's clearly visible that if we apply next operation on head of mainlist count number of times se will end up at desired first node of common occurence.

below is program ---->

#include <iostream>

using namespace std;

struct Node {

char value;

Node* next;

Node* prev;

};

Node* findList(Node* subList, Node* mainList) {
Node* head = NULL;
string main,sub;//main and sub are string representation of both lists
Node *head1=subList,*head2 = mainList;
while(head1!=NULL)
{
sub+=head1->value;
head1=head1->next;
}
while(head2!=NULL)
{
main+=head2->value;
head2=head2->next;
}

std::size_t count = main.find(sub);//to find first occurence of one string in other we used predefined find function
if (count==std::string::npos)//if sub is not substring of main return NULL
return NULL;
head = mainList;
for(int i=1;i<=count;i++)
head = head->next; //applying next operation count times
return head;
}

void printList(Node* node)
{
while (node != nullptr)
{
printf("%c ", node->value);
node = node->next;
}
}
Node *newNode(char key)
{
Node *temp = new Node;
temp->value= key;
temp->next = nullptr;
return temp;
}
int main() {
// this is the sublist
Node *a = newNode('A');
a->next = newNode('C');
a->next->next = newNode('T');
a->next->next->next = nullptr;

// this is the main list
Node *b = newNode('A');
b->prev = nullptr;
b->next = newNode('A');
b->next->prev = b;
b->next->next = newNode('C');
b->next->next->prev = b->next;
b->next->next->next = newNode('T');
b->next->next->next->prev = b->next->next;
b->next->next->next->next = newNode('G');
b->next->next->next->next->prev = b->next->next->next;
b->next->next->next->next->next = newNode('A');
b->next->next->next->next->next->prev = b->next->next->next->next;
b->next->next->next->next->next->next = nullptr;
printList(a);
cout << endl;
printList(b);
cout << endl;
Node *c = findList(a, b);
cout << c->value << endl;

return 0;
}

if this answer is helpful to you please give positive rating.if any doubts please provide comments i will clarify your doubts