C++反转链表（四种思路：数组记录、递归实现、循环实现、头删头插）_反转链表 c++

思路一:使用数组保存各个结点的指针，然后使用循环，实现各个指针的反向

这只是我自己想的一种方法，可能有些蠢，但是确实能够实现链表的反转。

#include<iostream>

using namespace std;

typedef struct node
{
	int data;
	struct node* next;
}*linklist,node;

int main() {
	//创建链表，元素为5个
	//这里主要是为了简单，没有使用头插法和尾插法，而是直接构造一个链表
	linklist head = new node;
	linklist n1p = new node;
	linklist n2p = new node;
	linklist n3p = new node;
	linklist n4p = new node;
	linklist n5p = new node;
	n1p->data = 1;
	n2p->data = 2;
	n3p->data = 3;
	n4p->data = 4;
	n5p->data = 5;
	head->next = n1p;
	n1p->next = n2p;
	n2p->next = n3p;
	n3p->next = n4p;
	n4p->next = n5p;
	n5p->next = NULL;
	
	if (head->next != NULL) {//保证链表非空
		//输出链表内容
		linklist p = head;
		int n = 0;
		while (p->next != NULL) {
			cout << p->next->data << endl;
			p = p->next;
			n++;
		}
		cout << endl;

		//把链表内容记录到数组中
		linklist* narr = new linklist[n];
		int i = 0;
		p = head;
		while (p->next != NULL) {
			narr[i++] = p->next;
			p = p->next;
		}

		//把数组中的内容输出
		for (i = 0; i < n; i++) {
			cout << narr[i]->data << endl;
		}
		cout << endl;

		//反转链表
		for (i = 0; i < n - 1; i++) {
			narr[i + 1]->next = narr[i];
		}
		narr[0]->next = NULL;
		head->next = narr[n - 1];

		//输出反转之后链表的内容
		p = head;
		while (p->next != NULL) {
			cout << p->next->data << endl;
			p = p->next;
		}
		cout << endl;
	}
	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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

思路二：使用递归实现

以自己对递归粗浅的认识写的，写的也很蠢，仅仅做记录

#include<iostream>

using namespace std;

typedef struct node
{
	int data;
	struct node* next;
}*linklist,node;

//反转链表的递归实现
void reverseLinkList(linklist& head,linklist& another) {
	//another是一个空链表的表头
	if (head->next == NULL) 
		return;
	reverseLinkList(head->next, another);
	linklist p = another;
	while (p->next != NULL) {
		p = p->next;
	}
	p->next = head->next;
	p->next->next = NULL;
}


int main() {
	//创建链表，元素为5个
	//这里主要是为了简单，没有使用头插法和尾插法，而是直接构造一个链表
	linklist head = new node;
	linklist n1p = new node;
	linklist n2p = new node;
	linklist n3p = new node;
	linklist n4p = new node;
	linklist n5p = new node;
	n1p->data = 1;
	n2p->data = 2;
	n3p->data = 3;
	n4p->data = 4;
	n5p->data = 5;
	head->next = n1p;
	n1p->next = n2p;
	n2p->next = n3p;
	n3p->next = n4p;
	n4p->next = n5p;
	n5p->next = NULL;
	
	if (head->next != NULL) {//保证链表非空
		//反转
		linklist another = new node;
		another->next = NULL;
		reverseLinkList(head, another);

		//输出
		linklist p = another;
		while (p->next != NULL) {
			cout<<p->next->data<<endl;
			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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

思路三：使用循环实现

#include<iostream>

using namespace std;

typedef struct node
{
	int data;
	struct node* next;
}*linklist,node;

int main() {
	//创建链表，元素为5个
	//这里主要是为了简单，没有使用头插法和尾插法，而是直接构造一个链表
	linklist head = new node;
	linklist n1p = new node;
	linklist n2p = new node;
	linklist n3p = new node;
	linklist n4p = new node;
	linklist n5p = new node;
	n1p->data = 1;
	n2p->data = 2;
	n3p->data = 3;
	n4p->data = 4;
	n5p->data = 5;
	head->next = n1p;
	n1p->next = n2p;
	n2p->next = n3p;
	n3p->next = n4p;
	n4p->next = n5p;
	n5p->next = NULL;
	
	if (head->next != NULL) {//保证链表非空
		linklist plast=nullptr;
		linklist pnow = head->next;
		linklist p=head->next;
		while (p!= nullptr) {
			p = p->next;

			//反转
			pnow->next = plast;
			
			plast = pnow;
			pnow = p;
		}
		//将链表的头结点放在原链表末尾结点之前
		head->next = plast;

		//输出
		p = head;
		while (p->next != nullptr) {
		cout<<p->next->data<<endl;
			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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

这个循环的思路其实我在看完一片递归实现反转链表的博客之后，自己转化之后写的
这个递归实现的博客原文请点击链接https://blog.csdn.net/Rick1860/article/details/82864091

思路四：对原链表使用头删法删除结点，对新链表使用头插法插入链表

#include<iostream>

using namespace std;

typedef struct node
{
	int data;
	struct node* next;
}*linklist,node;

int main() {
	//创建链表，元素为5个
	//这里主要是为了简单，没有使用头插法和尾插法，而是直接构造一个链表
	linklist head = new node;
	linklist n1p = new node;
	linklist n2p = new node;
	linklist n3p = new node;
	linklist n4p = new node;
	linklist n5p = new node;
	n1p->data = 1;
	n2p->data = 2;
	n3p->data = 3;
	n4p->data = 4;
	n5p->data = 5;
	head->next = n1p;
	n1p->next = n2p;
	n2p->next = n3p;
	n3p->next = n4p;
	n4p->next = n5p;
	n5p->next = NULL;
	
	if (head->next != NULL) {//保证链表非空
		linklist another = new node;
		another->next = nullptr;
		linklist p;//用来记录删除结点
		while (head->next != nullptr) {
			//头删法删除
			p = head->next;
			head->next = head->next->next;
			//头插法新增
			p->next = another->next;
			another->next = p;
		}

		//输出
		p = another;
		while (p->next != nullptr) {
		cout<<p->next->data<<endl;
			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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53