链表基本操作

分类

• 单链表

• 双链表

• 双向循环链表

基本操作

• 创建单链表

struct ListNode{
    int val;
    ListNode *next=NULL;
};

• 链表末尾插入元素data并返回

//尾插data
ListNode *insertNode_e(ListNode *head,int data)
{
    ListNode *newNode=new ListNode;
    newNode->val=data;
    ListNode *tempNode=head;
    if(!tempNode)
    {
        return newNode;

    }
    else
    {
        //遍历到尾结点
        while(tempNode->next)
        {
            tempNode=tempNode->next;
        }
        tempNode->next=newNode;
        return head;
    }

}

• 第i位置后插入元素data

//第i位置后插入data
ListNode *InsertNode_i(ListNode *head,int i,int data)
{
    ListNode *newNode=new ListNode;
    newNode->val=data;
    ListNode *p=head;
    int j=0;
    //遍历找到第i个结点或者没有
    while(p&&j<i-1)
    {
        p=p->next;
        j++;
    }
    //不存在p和i<1
    if(!p||j>i-1)
    {
        return 0;
    }
    else
    {
        newNode->next=p->next;
        p->next=newNode;
        return head;
    }
}

• 删除元素data

//删除值为data结点
ListNode *deleteNode(ListNode *head,int data)
{
    ListNode *tempNode=head;
    //是否为空链表
    if(!tempNode)
    {
        return head;
    }
    else
    {
        //是否要删除头结点
        if(tempNode->val==data)
        {
            head=tempNode->next;
            delete tempNode;
        }
        else
        {
            //找到data的前一个结点或者没有
            while(tempNode->next&&tempNode->next->val!=data){tempNode=tempNode->next;}
            //找到的情况下
            if(tempNode->next)
            {
                ListNode *p=tempNode->next;
                tempNode->next=p->next;
                delete p;
            }

        }
        return head;
    }
}

实验代码：

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
//创建一个链表
struct ListNode{
    int val;
    ListNode *next=NULL;
};

//尾插data
ListNode *insertNode_e(ListNode *head,int data)
{
    ListNode *newNode=new ListNode;
    newNode->val=data;
    ListNode *tempNode=head;
    if(!tempNode)
    {
        return newNode;

    }
    else
    {
        //遍历到尾结点
        while(tempNode->next)
        {
            tempNode=tempNode->next;
        }
        tempNode->next=newNode;
        return head;
    }

}
//第i位置后插入data
ListNode *InsertNode_i(ListNode *head,int i,int data)
{
    ListNode *newNode=new ListNode;
    newNode->val=data;
    ListNode *p=head;
    int j=0;
    //遍历找到第i个结点或者没有
    while(p&&j<i-1)
    {
        p=p->next;
        j++;
    }
    //不存在p和i<1
    if(!p||j>i-1)
    {
        return 0;
    }
    else
    {
        newNode->next=p->next;
        p->next=newNode;
        return head;
    }
}


//删除值为data结点
ListNode *deleteNode(ListNode *head,int data)
{
    ListNode *tempNode=head;
    //是否为空链表
    if(!tempNode)
    {
        return head;
    }
    else
    {
        //是否要删除头结点
        if(tempNode->val==data)
        {
            head=tempNode->next;
            delete tempNode;
        }
        else
        {
            //找到data的前一个结点或者没有
            while(tempNode->next&&tempNode->next->val!=data){tempNode=tempNode->next;}
            //找到的情况下
            if(tempNode->next)
            {
                ListNode *p=tempNode->next;
                tempNode->next=p->next;
                delete p;
            }

        }
        return head;
    }
}
//输出链表
void outNode(ListNode *head)
{
    while(head)
    {
        cout<<head->val<<"	";
        head=head->next;
    }
    cout<<endl;
    return;
}



class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode *p=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return p;
    }
};

int main()
{
    ListNode *head=new ListNode;
    int num=6;
    head=NULL;
    //尾插法生成降序长度为5的链表head
    while(--num)
    {
        head=insertNode_e(head,num);
    }
    cout<<"链表:		";
    outNode(head);
    cout<<"第2后插入123	";
    head=InsertNode_i(head,2,123);
    ListNode *head2=head;
    outNode(head);
    cout<<"删除123后	";
    head2=deleteNode(head2,123);
    outNode(head2);

}