C++单链表创建、遍历、插入、删除结点、整体删除、反转

单链表的定义

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

创建单链表

void creatlist(ListNode*head,int N) {
	ListNode *pre = head;
	cin >> head->val;
	for (int i = 0; i < N-1; i++)
	{
		ListNode *ls = new ListNode;
		cin >> ls->val;
		ls->next = NULL;
		pre->next = ls;
		pre = ls;
	}
}

单链表遍历

void readlist(ListNode *head,int N) {
	ListNode*a;
	a = head;
	for (int i = 0; i < N; i++)
	{
		cout << a->val << " ";
		a = a->next;
	}
}

单链表插入结点

bool insertlist(ListNode*head, int n, int vals)
{
	int j = 1;
	ListNode*pp; ListNode*s;
	pp = head;
	while (pp&&j < n)
	{
		pp = pp->next;
		++j;
	}
	if (!pp || j > n) return false;
	s = new ListNode;
	s->val=vals;
	s->next = pp->next;
	pp->next = s;
	return true;
}

单链表删除结点

bool deletelist(ListNode * head, int i)
{
	int x = 1;
	ListNode*p2 = head;
	ListNode*q2;
	while (p2->next&&x < i)
	{
		p2 = p2->next;
		++x;
	}
	if (!(p2->next) || x > i) return false;
	q2 = p2->next;
	p2->next = q2->next;
	delete q2; 
	return true;
}

单链表整体删除

bool clearlist(ListNode*head)
{
	ListNode*p;
	ListNode*q;
	p = head;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;

	}
	return true;
}

示例

#include <iostream>
#include <string>
#include <vector>
#include "stdio.h"
using namespace std;
struct ListNode
{
	int val;
	ListNode *next;
};
void creatlist(ListNode*head,int N) {
	ListNode *pre = head;
	cin >> head->val;
	for (int i = 0; i < N-1; i++)
	{
		ListNode *ls = new ListNode;
		cin >> ls->val;
		ls->next = NULL;
		pre->next = ls;
		pre = ls;
	}
}
void readlist(ListNode *head,int N) {
	ListNode*a;
	a = head;
	for (int i = 0; i < N; i++)
	{
		cout << a->val << " ";
		a = a->next;
	}
}
ListNode * reverselist(ListNode*head)
{
	if (head == nullptr)return head;
	ListNode *dummy = new ListNode;
	dummy->next = head;
	ListNode*prev = head;
	ListNode*pcur = prev->next;
	while (pcur!=nullptr)
	{
		prev->next = pcur->next;
		pcur->next = dummy->next;
		dummy->next = pcur;
		pcur = prev->next;
	}
	return dummy->next;

}
bool clearlist(ListNode*head)
{
	ListNode*p;
	ListNode*q;
	p = head;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;

	}
	return true;
}
bool insertlist(ListNode*head, int n, int vals)
{
	int j = 1;
	ListNode*pp; ListNode*s;
	pp = head;
	while (pp&&j < n)
	{
		pp = pp->next;
		++j;
	}
	if (!pp || j > n) return false;
	s = new ListNode;
	s->val=vals;
	s->next = pp->next;
	pp->next = s;
	return true;
}

bool deletelist(ListNode * head, int i)
{
	int x = 1;
	ListNode*p2 = head;
	ListNode*q2;
	while (p2->next&&x < i)
	{
		p2 = p2->next;
		++x;
	}
	if (!(p2->next) || x > i) return false;
	q2 = p2->next;
	p2->next = q2->next;
	delete q2; 
	return true;
}

int main()
{
	ListNode *head = new ListNode;
	int N = 0;
	cout << "输入链表长度" << endl;
	cin >> N;
	cout << "创建链表" << endl;
	creatlist(head, N);
	cout << "读取链表" << endl;
	readlist(head, N);
	cout << endl;
	cout << "清空链表" << endl;
	//cout << clearlist(head) << endl;
	cout << "插入链表" << endl;
	cout << insertlist(head,2,4) << endl;
	readlist(head, N+1);
	cout <<endl<< "单链表节点删除" << endl;
	cout << deletelist(head,2) << endl;
	readlist(head, N);
	cout << endl;
	cout << "反转链表" << endl;
	ListNode *rever = reverselist(head);
	readlist(rever, N); cout << endl;
	return 0;
}