Linked Lists

Question 1

Reverse a doubly linked list O(n)

Answer 1

void reverse(Node **head_ref)
{
    Node *next=NULL,*curr;
    curr = *head_ref;
    while(curr!=NULL)
    {
        if(curr->next==NULL)
        {
            *head_ref = curr;
        }
        next = curr->next;
        curr->next = curr->prev;
        curr->prev = next;
        curr=next;
    }
}

Question 2

Reverse a singly linked list O(n)

Answer 2

Node* reverseList(Node *head)
{
    Node* prev,*curr,*next;
    prev=next=NULL;
    curr=head;
    while(curr!=NULL)
    {
        next = curr->next;
        curr->next=prev;
        prev=curr;
        curr=next;
    }
    head=prev;
    return head;
}

Question 3

Detect loop in a linked list O(n)

Answer 3

int detectloop(Node *head) {

    Node *fast,*slow;
    fast=head;
    slow=head;
    while(slow && fast && fast->next)
    {
        slow=slow->next;
        fast = fast->next->next;
        if(slow==fast)
        {
            return 1;
        }
    }
    return 0;
}

Question 4

Intersection of two linked lists and return in sorted form O(mn). Other methods - merge sort and hashing

Answer 4

struct node* findIntersection(struct node* head1, struct node* head2)
{
    vector v;
    int count[1000000];
    memset(count,0,sizeof(count));
    while(head1!=NULL)
    {
        count[head1->data]++;
        head1=head1->next;
    }
    while(head2!=NULL)
    {
        if(count[head2->data]>=1)
        {
            v.push_back(head2->data);
        }
        head2=head2->next;
    }
    node* newhead;
    newhead=NULL;
    sort(v.begin(),v.end(),greater());
    for(int i=0;idata = v[i];
        ptr->next = NULL;
        if(newhead==NULL)
        {
            newhead = ptr;
        }
        else
        {
            ptr->next = newhead;
            newhead = ptr;
        }
    }
    return newhead;
}

Question 5

Intersection point of two linked lists O(m+n)

Answer 5

int intersectPoint(Node* head1, Node* head2)
{
    int m=0,n=0;
    Node* temp = head1;
    while(head1!=NULL)
    {
        n++;
        head1=head1->next;
    }
    head1=temp;
    temp = head2;
    while(head2!=NULL)
    {
        m++;
        head2=head2->next;
    }
    head2=temp;
    Node* temp1;
    Node* temp2;
    int diff=0;
    if(n>=m)
    {
        temp = head1;
        temp2 = head2;
    }
    else
    {
        temp = head2;
        temp2 = head1;
    }
    while(diffnext;
        diff++;
    }
    temp1=temp;
    while(temp1 && temp2)
    {
        if(temp1==temp2)
        {
            return temp1->data;
        }
        temp1=temp1->next;
        temp2=temp2->next;
    }
    return -1;
}