c++ 链表的创建与链表常见操作_c++链表的创建与操作

c++ 链表的创建与链表常见操作

一、链表定义(struct)
下面的结构体定义了C++语言中的一种常见的链表节点，包括数据、指针和两种种不同类型的构造函数。

struct ListNode {
    int val;        //存储数据
    ListNode *next; //next指针
    ListNode() : val(0), next(NULL) {}  //类似构造函数
    ListNode(int x) : val(x), next(NULL) {}
};
1
2
3
4
5
6

二、节点创建
通过定义上述的节点结构，便可通过下述三种方法实现一个节点的创建。

int main()
{
    ListNode *node1 = new ListNode;
    ListNode *node2 = new ListNode();   // 初始化值为0
 	ListNode *node3 = new ListNode(100); // 初始化值为100

 	cout<< node1->val<<endl;
 	cout<< node2->val<<endl;
    cout<< node3->val<<endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

三、插入节点

int main()
{
 	ListNode *node1 = new ListNode(100); // 初始化值为-1
 	ListNode *node2 = new ListNode(200); // 初始化值为-1

 	node1->next=node2;

 	cout<< node1->next->val<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10

四、循环建立链表

int main()
{
 	ListNode *head = new ListNode(); //头节点
    ListNode *p=head;                //指针
    int i=1;
    while(i<5){
        ListNode *node = new ListNode(i); // 初始化一个节点
        p->next = node;
        p=p->next;
        i++;
    }
    p->next=NULL;//最后一个节点的指针指向空
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

五、遍历链表

int main()
{
 	ListNode *head = new ListNode(); //头节点
    ListNode *p=head;                //指针
    int i=1;
    while(i<5){
        ListNode *node = new ListNode(i); // 初始化一个节点
        p->next = node;
        p=p->next;
        i++;
    }
    p->next=NULL;//最后一个节点的指针指向空
    
    
    //遍历链表部分
    p=head;
    while(p){
        cout<<p->val;
        p=p->next;
    }
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

六、删除节点

int main()
{
 	ListNode *head = new ListNode(); //头节点
    ListNode *p=head;                //指针
    int i=1;
    while(i<5){
        ListNode *node = new ListNode(i); // 初始化一个节点
        p->next = node;
        p=p->next;
        i++;
    }
    p->next=NULL;//最后一个节点的指针指向空
    p=head;

    //删除第二个节点
    ListNode *pre = p->next;
    p->next=p->next->next;
    delete pre;


    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23