Finding corrupted node in two linked list

How to find the corrupted node in two linked list:





Algorithm:

 solution 1:

 By using hash table we can find when traversing list1 store in hash table and when traversing
second list check whether next address is present in hashtable or not if present address present hashtable that is first corrupted node
time complexity: O(m+n)
space complexity: O(m) or O(n) depends on which list u are storing in hashtable

solution 2:(which possible in only c not possible in java )
Traverse list1 once while traversing make next address of each node negative then move
after that start traverse second linked list untill u find next address as negative that node is first corrupted of two linkedlist

time complexity:O(m+n)
space complexity:O(1)

note: practically we wont get this situation of corrupting i intentionally made corruption between
two linkedlists  then i find that node by using above logic

code for second solution:

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct node
{
    int data;
    struct node *next;
} *head1=NULL,*head2=NULL;

struct node * insertlist1(struct node *head,struct node *inter,int i,int k)
{
    struct node *temp,*q;   
    temp=(struct node *)malloc(sizeof(struct node));
    if(k==5)
    {
        inter=temp;
        }
    temp->data=i;
        temp->next=NULL;
    if(head->next==NULL)
    {
        head->next=temp;
       
        }
        else
        {
            q=head->next;
            while(q->next!=NULL)
            q=q->next;
            q->next=temp;
            }
            return inter;
}

//displaying nodes with address because we can see where nodes are corruping
void display(struct node *head)
{
    struct node *temp;
    temp=head->next;
    while(temp->next!=NULL)
    {
        printf("%u | %d | %u    ",temp,temp->data,temp->next);
        temp=temp->next;
        }
    }
   
    //insertion 2
insertlist2(struct node *head,struct node *inter,int i,int k)
{
    struct node *temp,*q;       
    if(k==5)
    {
        temp=inter;
        temp->data=i;
        q=head->next;
        while(q->next!=NULL)
        q=q->next;
        q->next=temp;
        printf("successfully corrupted node maden");
       
        }
    else if(k<5)
{
temp=(struct node *)malloc(sizeof(struct node));

        temp->data=i;
        temp->next=NULL;
    if(head->next==NULL)
    {
        head->next=temp;
       
        }
        else
        {
            q=head->next;
            while(q->next!=NULL)
            q=q->next;
           
            q->next=temp;
            }
}
}

void findcorrupt(struct node *head1,struct node *head2)
{
  
    struct node *temp,*q;
    temp=head1->next;          
    while(temp->next!=NULL)
    {
        q=temp;
        temp=temp->next;
        q->next=((unsigned int)q->next)*-1;
        }  
    temp=head2->next;
    while((int)temp->next>0)
    {
        temp=temp->next;
        }
           
            printf("%d is comman",temp);
            }
       


int main()
{
    int i=1,j,k=1,m=3;
    head1=(struct node*)malloc(sizeof(struct node));
    head1->next=NULL;
    head2=(struct node*)malloc(sizeof(struct node));
    head2->next=NULL;
    struct node *inter=NULL;
    while(i)
    {
    printf("\n enter 1 insert element in list1");
    printf("\n enter 2 insert element in list2");
    printf("\n enter 3 to display list1");
    printf("\n enter 4 to display list2");
    printf("\n enter 5 find corrupted node");
    printf("\n enter 0to exit");
    scanf("%d",&i);
   
    switch(i)
    {
    case 1:
        printf("enter elementtoinsert");
        scanf("%d",&j);
        inter=insertlist1(head1,inter,j,k++);
        break;
       
    case 2:
        printf("enter element to insert");
        scanf("%d",&j);
        insertlist2(head2,inter,j,m++);
        break;
       
    case 3:
        display(head1);
        break;
       
    case 4:
        display(head2);
        break;
       
    case 5:
        findcorrupt(head1,head2);
        break;
       
        }
    }
}