#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
class Node
{
public:
    int data;
    Node* next;
};

Node* create(int A[],int n)
{
    int i;
    Node* t, *last;
    Node* head;
    head = new Node;
    head->data = A[0];
    head->next = NULL;
    last = head;
    for(i=1;i<n;i++)
    {
        t = new Node;
        t->data = A[i];
        t->next =NULL;
        last->next = t;
        last = t;
    }
    return head;
}
Node* Lsearch(Node* p, int key)
{
    Node* q;
    while(p!=NULL)
    {
        if (key == p->data)
        {
            q->data = p->data;
            return q;
        }
        q=p;
        p=p->next;
    }
    return NULL;
}
Node* Rsearch(Node* p, int key)
{
    if(p==NULL)
        return NULL;
    if(key==p->data)
        return p;
    return Rsearch(p->next,key);
}
int main()
{
    int A[]={3,8,7,10,25,8,32,2};
    Node* temp; // 새로 new, heap에 생성할 필요없이 카피할 데이터는 포인터만 하면 된다.
    Node* result;
    temp = create(A,sizeof(A)/sizeof(A[0]));
    result = Lsearch(temp, 8);
    cout<<result->data<<endl;
    return 0;

}

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
class Node
{
public:
    int data;
    Node* next;
};

Node* create(int A[],int n)
{
    int i;
    Node* t, *last;
    Node* head;
    head = new Node;
    head->data = A[0];
    head->next = NULL;
    last = head;
    for(i=1;i<n;i++)
    {
        t = new Node;
        t->data = A[i];
        t->next =NULL;
        last->next = t;
        last = t;
    }
    return head;
}
Node* insert_(Node* p, int index, int x)
{
    Node* temp;
    int i;
    if(index<0 || index>8)
        return p;
    temp = new Node;
    temp->data = x;
    if(index == 0)
    {
        temp->next = p;
        p = temp;
    }
    else
    {
        for(i=0;i<index-1;i++)
            p=p->next;
        temp->next = p->next;
        p->next = temp;
    }
    return p;
}
void Display(Node* p)
{
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}
int main()
{
    int A[]={3,8,7,10,25,8,32,2};
    Node* temp;
    temp = create(A,sizeof(A)/sizeof(A[0]));
    insert_(temp,2,5);
    Display(temp);
    return 0;
}

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
class Node
{
public:
    int data;
    Node* next;
};

void insert_(Node* p, int index, int x)
{
    Node* temp;
    int i;
    if(index<0 || index>8)
        return;
    temp = new Node;
    temp->data = x;
    if(index == 0)
    {
        temp->next = p->next;
        p->next = temp;
    }
    else
    {
        for(i=0;i<index-1;i++)
            p=p->next;
        temp->next = p->next;
        p->next = temp;
    }
}
void Display(Node* p)
{
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}
int main()
{
    Node* head;
    head = new Node;
    insert_(head,0,15);
    insert_(head,0,8);
    insert_(head,0,9);
    insert_(head,2,10);
    Display(head);
    return 0;
}

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
class Node
{
public:
    int data;
    Node* next;
};
Node* create(int A[],int n)
{
    int i;
    Node* t, *last;
    Node* head;
    head = new Node;
    head->data = A[0];
    head->next = NULL;
    last = head;
    for(i=1;i<n;i++)
    {
        t = new Node;
        t->data = A[i];
        t->next =NULL;
        last->next = t;
        last = t;
    }
    return head;
}
void sorted_insert(Node* p, int x)
{
    Node* temp,*q=NULL;
    Node* head;
    temp = new Node;
    temp->data = x;
    temp->next =NULL;
    head = p;
    if(head==NULL)
    {
        head=temp;
    }
    else
    {
        while(p&&p->data<x)
        {
            q=p;
            p=p->next;
        }
        if(p==head)
        {
            temp->next = head;
            head = temp;
        }
        else
        {
            temp->next = q->next;
            q->next = temp;
        }
    }
}
void Display(Node* p)
{
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}
int main()
{
    int A[]={10,20,30,40,50};
    Node* head;
    head = create(A,5);
    sorted_insert(head,15);
    Display(head);
    return 0;
}

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
class Node
{
public:
    int data;
    Node* next;
};
Node* create(int A[],int n)
{
    int i;
    Node* t, *last;
    Node* head;
    head = new Node;
    head->data = A[0];
    head->next = NULL;
    last = head;
    for(i=1;i<n;i++)
    {
        t = new Node;
        t->data = A[i];
        t->next =NULL;
        last->next = t;
        last = t;
    }
    return head;
}
void RemoveDuplicate(Node* p)
{
    Node* q;
    q = p->next;
    while(q!=NULL)
    {
        if(p->data!=q->data)
        {
            p=q;
            q=q->next;
        }
        else
        {
            //dupicated
            p->next = q->next;
            free(q);
            q = p->next;
        }
    }
}
void Display(Node* p)
{
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}
int main()
{
    int A[]={10,20,20,40,50,50,50,60};
    Node* head;
    head = create(A,8);
    RemoveDuplicate(head);
    Display(head);
    return 0;
}