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.

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;
}

program snapshot

output snapshot