线性表

标签：head ListNode cur val int next 线性表

顺序表的存、读数据时的时间复杂度为o(1)；

插入删除时的时间复杂度为o(n);

比较适合元素个数不太变化的应用

链表的定义

struct  ListNode{
    int val;//结点储存的值
    ListNode *next;//指向下一个结点的指针
    ListNode(int x): val(x),next(NULL){}//结点的构造函数
};

 

单链表

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode() : val(0), next(nullptr) {}  *     ListNode(int x) : val(x), next(nullptr) {}  *     ListNode(int x, ListNode *next) : val(x), next(next) {}  * };  */ class Solution { public:     ListNode* removeElements(ListNode* head, int val) {     while (head != NULL && head->val == val) {              ListNode* tmp = head;             head = head->next;             delete tmp;         }
        // 删除非头结点         ListNode* cur = head;              //单链表的头结点是一个独立的内存，创建临时结点是为了修改后面的结点，而遍历时还需要从头结点开始，所有不能直接改变头节点的值         while (cur != NULL && cur->next!= NULL) {             if (cur->next->val == val) {                 ListNode* tmp = cur->next;                 cur->next = cur->next->next;                 delete tmp;             } else {                 cur = cur->next;             }         }         return head;
    } };   添加链表结点

 1、若令C为p，D为p->next,F为s则

s->next=p_next;

p-next=s;

顺序不能改变，因为如果我们先改变p的指向，则s无法找到p->next的地址,就会变成s->next=s;

 

在堆区开辟空间new

int* a=new int(10) 

返回的是指针

int *a=new int[10]

开辟数组，返回的是首地址

while(cur)

while里面存在指针，当指针为空时，退出循环

 

 

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

//递归写法

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur)
    {
        if(cur==NULL) return pre;
        ListNode* tmp=cur->next;
        cur->next=pre;

        return reverse(cur,tmp);
    }

    ListNode* reverseList(ListNode* head) {
        return reverse(NULL,head);//返回的是头结点
    }
};

 

 

 

标签：head,ListNode,cur,val,int,next,线性表
From： https://www.cnblogs.com/gaishuobulao/p/17342052.html