[大力庆祝国庆节] c / c ++实现单个链接列表的创建，插入，删除，倒置和合并

因为我要为入学考试做准备c/c++链表，所以前端的事物所占比例将变小，但是它仍然是与计算机相关的内容，因此每个人都知道. 当然，最近对901数据结构和算法设计进行了回顾，这也是大型公司笔试问题的一部分. 主要代码是c / c ++，因为已经四年没有写了，而且笔迹突然很渣==如果有任何需要改进的地方，请留言，我会及时进行修改.

点击github原始图片上传图片失败

[图像上传失败...（image-85d3-1538919156505）]

#include<iostream>
#include "stdio.h"
#include "stdlib.h"
using namespace std;
struct LNode{
    int data; // 数据域 
    LNode *next; // 指向自身的指针域 
};
typedef LNode *LinkList; 
LinkList createLinkList Head(){
LinkList L;
LinkList p;
int x;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
cin>> x;
while(x!=0) {
    p=(LinkList)malloc(sizeof(LNode));
    p->data=x;
    p->next=L->next;
    L->next=p;
    cin>>x;
};
return L;
}
int main(){
createLinkListHead();
}

LinkList findNodeByOrder(LinkList L,int target){
    LinkList p=L;
    int i=0;
    while(i<target&&p->next!=NULL){
        p=p->next;
        i++;
    }
    if(i==target){
        return p;
    }
    return NULL;
}

int findNodeByValue(LinkList L,int target){
    LinkList p=L;
    while(p->data!=target&&p->next!=NULL){
        p=p->next;
    }
    
    return p->data;
}

LinkList insertBefore(LinkList L,int s,int target){ // target为指定插入位置的数据域为s的节点 
    LinkList p=L;
    LinkList newNode=(LinkList)malloc(sizeof(LNode));
    newNode->data=s;
    int i=0; 
    if(target<1){
        printf("参数target错误"); 
        exit(1);
    }
    while(i<target-1){
        i++;
        p=p->next;
    }
        // 现在的p是目标节点的前驱 
        newNode->next=p->next;
        p->next=newNode;
    return L;
}

LinkList deleteByOrder(LinkList L,int i){
    // 仍然是找前驱 
    LinkList p=L;
    LinkList q;
    int j=0;
    while(j<i-1){
        p=p->next; 
        j++;
    }
    if(p==NULL||j>i-1){
        printf("参数i错误");
        exit(1);
    } 
    q=p->next; // 目标节点
    p->next=q->next;
    free(q);
    return L;
}

struct DuLNode{
    int data;
    DuLNode *next;
    DuLNode *prior;
}; 
typedef DuLNode *DuLinkList;
DuLinkList createDoubleLinkList(){
    DuLinkList head,L;
    DuLinkList p;
    int x;
    L=(DuLinkList)malloc(sizeof(DuLNode));
    head=L;
    cin>>x;
    while(x!=0){
        p=(DuLinkList)malloc(sizeof(DuLNode));
        p->data=x;
        p->next=NULL;
        p->prior=L;
        L->next=p;
        L=p; 
        cin>>x;
    }
    return head;
}

在双向链表的第i个节点之前插入一个带有数据字段x的节点. 它仍然首先连接，然后断开，因为双向链表具有前置指针c/c++链表，因此没有必要查找第i + 1个元素. 首先连接新节点s的前任，然后断开目标节点p的前任节点的后继指针，将其连接到s，然后操作目标节点p的前任指向新节点！ !!

DuLinkList DuLinkInsert(DuLinkList L,int i,int x){
    DuLinkList head,s,p;
    int n=0;
    p=L;
    head=L;
    s=(DuLinkList)malloc(sizeof(DuLNode));
    s->data=x; 
    while(n<i){
        p=p->next;
        n++;
    }
    if(i==n){
        s->next=p;
        s->prior=p->prior;
        p->prior->next=s;
        p->prior=s;
        return head;
    }else{
        cout<<"参数i错误"<<endl;
        exit(1);
    }
}

删除位置i处的节点p. p的前任与p的后继相同. p的前任连接到p的前任指针，并释放p.

DuLinkList DuLinkDelete(DuLinkList L,int i){
    DuLinkList head,p;
    int n=0;
    p=L;
    head=L;
    while(n<i){
        p=p->next;
        n++;
    }
    if(i==n){
        p->prior->next=p->next;
        p->next->prior=p->prior;
        free(p);
        return head;
    }else{
        cout<<"参数i错误"<<endl;
        exit(1);
    }
}

Node* mergelistByOrder(Node *l1,Node *l2){
    Node *head,*L;
    L=new Node;
    L->next=NULL;
    L->data=0;
    head=L;
    while(l1&&l2){
        if(l1->data<l2->data){
            L->next=l1;
            l1=l1->next;
        }else{
            L->next=l2;
            l2=l2->next;    
        }
        L=L->next;
    }
    if(l1){
        L->next=l1;
    }
    if(l2){
        L->next=l2;
    }
    return head->next;
}

就地反转需要两个指针p，q和一个临时指针t. q是p的后继，然后将q->指向p旁边. 在循环的最后，首先断开头节点和链接列表之间的后继关系，并将头节点的后继指向p. 有关详细信息，请参阅此图标->反向链接列表

Node* reverse(Node* L){
    Node *p,*q,*t,*head;
    head=L;
    p=head->next;
    q=head->next->next;
    while(q!=NULL){
    t = q->next;  
    q->next = p;  
    p = q;  
    q = t;
    }
    head->next->next=NULL;
    head->next=p;
    return head;
}

第一种方法是组合以上两种方法，先按顺序合并它们，然后将它们反向. 第二种方法是使用标头插入方法来选择最小的一种，然后首先插入.

Node* mergelistByDescOrder(Node *l1,Node *l2){
    Node *L,*head,*t,*q;
    L=new Node();
    head=L;
    while(l1&&l2){
        if(l1->data<l2->data){
            t=l1;
            l1=l1->next;
        }else {
            t=l2;
            l2=l2->next;
        }
        t->next=L->next;
        L->next=t;
        //L=t;
        t=NULL; 
    }
    // 如果l1和l2循环之后还有剩余的节点，按顺序依次添加到头节点之后
    if(l1){
        t=l1;
    }
    if(l2){
        t=l2;
    }
    while(t){
        q=t;
        t=t->next;
        q->next=L->next;
        L->next=q;
    }
    return head->next;
} 

那房子起水泡

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-154521-1.html