#include <bits/stdc++.h>
using namespace std;
 
typedef struct node
{
    int data;
    struct node *next;
}no;
 
int main()
{
    no *head,*tail,*p,*q;
    head=new no;
    head->next=NULL;
    tail=head;
    int n;
    printf("一共要輸入的數：");
    cin>>n;
    int k;
    cin>>k;
    for(int i=0;i<n;i++)
    {
        p=new no;
        p->data=k;
        p->next=NULL;
        tail->next=p;//因為tail=head,所以tail沒有數值，tail->next才有數值
        tail=p;
        cin>>k;
    }
    printf("輸入要插入的數：");
    int m;
    cin>>m;
    q=new no;//生成一個結點來存放這個數
    q->data=m;
    q->next=NULL;
    printf("要插在哪個數和哪個數之間：");
    int a,b;
    cin>>a>>b;
    p=head;
    while(p->data!=m&&p->next!=NULL)
    {
       p=p->next;
       if(p->data==a&&p->next->data==b)
       {
           q->next=p->next;//先處理后面的結點，保證后面的鏈表不斷開,
           //q->next可以起到鏈接后面鏈表的作用
           p->next=q;
       }
    }
    p=head->next;
    for(int j=0;j<n+1;j++)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    return 0;
}

int inserFrontLinklist(struct Test* head,struct Test* new,int data1)
{
?? ?struct Test* point = head;
?? ?while(point != NULL)
?? ?{
?? ??? ?if(point->data == data1)
?? ??? ?{
?? ??? ??? ?//后插法的做法
?? ??? ??? ?new->next = point->next;
?? ??? ??? ?point->next = new;
?? ??? ??? ?return 1;
?? ??? ?}
?? ??? ?point = point->next;
?? ?}?? ?
?? ?return 0;
}

?? ?struct Test* point = head;
?? ?if(point->data == data)
?? ?{
?? ??? ?new->next = head;
?? ??? ?return new;
?? ?}//如果要找的那個數剛好在頭結點的話那么直接插進去即可

while(point->next != NULL)//這里跟后插法的區別，后插法是直接判斷point本身，而這里是判斷point->next
?? ?{
?? ??? ?if(point->next->data == data)//這里也一樣，后插法是判斷point->data,而這里是判斷point->next->data;
?? ??? ?{
?? ??? ??? ?new->next = point->next;//這里的算法跟后插法一樣
?? ??? ??? ?point->next = new;
?? ??? ??? ?
?? ??? ??? ?printf("Congratulations,you find the data success!\n");
?? ??? ??? ?return head;
?? ??? ?}
?? ??? ?point = point->next;
?? ?}

struct Test* insertBehindLinklist(struct Test *head,struct Test* new,int data)
{//前插法的做法
?? ?struct Test* point = head;
?? ?if(point->data == data)
?? ?{
?? ??? ?new->next = head;
?? ??? ?return new;
?? ?}//如果要找的那個數剛好在頭結點的話那么直接插進去即可。
?? ?
?? ?while(point->next != NULL)//這里跟后插法的區別，后插法是直接判斷point本身，而這里是判斷point->next
?? ?{
?? ??? ?if(point->next->data == data)//這里也一樣，后插法是判斷point->data,而這里是判斷point->next->data;
?? ??? ?{
?? ??? ??? ?new->next = point->next;//這里的算法跟后插法一樣
?? ??? ??? ?point->next = new;
?? ??? ??? ?
?? ??? ??? ?printf("Congratulations,you find the data success!\n");
?? ??? ??? ?return head;
?? ??? ?}
?? ??? ?point = point->next;
?? ?}
?? ?printf("Sorry, you find error!\n");
?? ?
?? ?return head;
}