目录

前言：

一，反转一个链表(迭代)

 二，打印一个链表（递归）

三，反转一个链表(递归)

四，双向链表

总结

---

前言：

我们根据 [文章  链表1] 可以知道链表相比较于数组的优缺点和计算机是如何管理内存的，然后介绍了链表的实现，头插法，任意节点插入，任意节点删除，接下来我们就来学习反转链表与打印链表的迭代和递归操作

---

 

一，反转一个链表(迭代)

反转一个链表并不是移动位置，而是改变输出方向，就好比如数组一样，我们打印一个反转的数组，就是for循环反着循环就好了，取决于下角标，而不是数据的位置，这里也是同理 

#include<iostream>
#include<new>
using namespace std;

struct Node {
	int data;
	Node* Next;
};

Node* head;


void reverse(){
	Node* current, * prev, * next;
	current = head;  prev = NULL;
	while (current != NULL) {
		next = current->Next;
		current->Next = prev;  //这里可以设置第一个节点为NULL
		prev = current;
		current = next;
	}
	head = prev;
}


void print() {
	Node* temp = head;
	while(temp!=NULL) {
		cout << temp->data << "  ";
		temp = temp->Next;
	}
}


int main() {
	head = NULL;
	Node* temp1 = new Node;
	temp1->data = 1;
	temp1->Next = NULL;

	Node* temp2 = new Node;
	temp2->data = 2;
	temp2->Next = NULL;

	Node* temp3 = new Node;
	temp3->data = 3;
	temp3->Next = NULL;

	Node* temp4 = new Node;
	temp4->data = 4;
	temp4->Next = NULL;

	temp1->Next = temp2;  temp2->Next = temp3;  temp3->Next = temp4;
	head = temp1;
	reverse();
	print();
}

这是反转一个链表的操作，然后我们来详细的看一下这个反转链表的函数

void reverse(){
	Node* current, * prev, * next;
	current = head;  prev = NULL;
	while (current != NULL) {
		next = current->Next;
		current->Next = prev;  //这里可以设置第一个节点为NULL
		prev = current;
		current = next;
	}
	head = prev;
}

这里就是反转链表的函数，我们反转链表主要就是利用改变后面的指向，使得输出方向发生变化，因为head永远都是这个链表的第一个节点的位置

这里设置了三个指针

prev：    先前的      这个是用来当current为空的时候，好用prev给head提供最好一个节点的位置，还有一个就是让current指向前一个

current：现在的      这个是用来表示现在这个节点的，利用current来来指向前一个

next：    下一个的   这个是用来为current提供下一个位置的

 二，打印一个链表（递归）

 这里就不讲解递归的思想了，可以去看我的文章函数的递归

我们根据这个思想来编写这个递归思想书写这个代码

#include<iostream>
#include<new>
using namespace std;

struct Node {
	int data;
	Node* Next;
};

Node* head;

void reverse(){
	Node* current, * prev, * next;
	current = head;  prev = NULL;
	while (current != NULL) {
		next = current->Next;
		current->Next = prev;  //这里可以设置第一个节点为NULL
		prev = current;
		current = next;
	}
	head = prev;
}

void print1(Node* p) {
	if (p == NULL) {
		return;
	}
	cout << p->data << " ";
	print1(p -> Next);
	cout << p->data << " ";
}

int main() {
	head = NULL;
	Node* temp1 = new Node;
	temp1->data = 1;
	temp1->Next = NULL;

	Node* temp2 = new Node;
	temp2->data = 2;
	temp2->Next = NULL;

	Node* temp3 = new Node;
	temp3->data = 3;
	temp3->Next = NULL;

	Node* temp4 = new Node;
	temp4->data = 4;
	temp4->Next = NULL;

	temp1->Next = temp2;  temp2->Next = temp3;  temp3->Next = temp4;
	head = temp1;
	reverse();
	print1(head);
}

这个里面有利用递归来书写的打印链表

if (p == NULL) {
	return;
}

这个为递归的基准条件，什么时候跳出递归进行反转

cout << p->data << " ";
print1(p -> Next);
cout << p->data << " ";

这个是递归的过程，上面的为正序打印，下面为逆序打印，至于为什么这样，看我的文章函数的递归

三，反转一个链表(递归)

#include<iostream>
#include<new>
using namespace std;

struct Node {
	int data;
	Node* Next;
};

Node* head;

void reverse1(Node*p){
	if (p->Next == NULL) {
		head = p;
		return;
	}
	reverse1(p->Next);
	Node* q = p->Next;
	q->Next = p;
	p->Next = NULL;
}

void print1(Node* p) {
	if (p == NULL) {
		return;
	}
	cout << p->data << " ";
	print1(p -> Next);
}

int main() {
	head = NULL;
	Node* temp1 = new Node;
	temp1->data = 1;
	temp1->Next = NULL;

	Node* temp2 = new Node;
	temp2->data = 2;
	temp2->Next = NULL;

	Node* temp3 = new Node;
	temp3->data = 3;
	temp3->Next = NULL;

	Node* temp4 = new Node;
	temp4->data = 4;
	temp4->Next = NULL;

	temp1->Next = temp2;  temp2->Next = temp3;  temp3->Next = temp4;
	head = temp1;
	reverse1(head);
	print1(head);
}

我们来看这个递归反转链表的代码

void reverse1(Node*p){
	if (p->Next == NULL) {
		head = p;
		return;
	}
	reverse1(p->Next);
	Node* q = p->Next;
	q->Next = p;
	p->Next = NULL;
}

这个相较于迭代，代码量少了很多

if语句是用来设置基准条件的，着p是为了寻找最后一个节点赋值给head，另外一个就是挖掘深度，提供可以改变指向的一个环境，后面就是递归完之后，我们知道这个如果是打印数字的话就是反着来的，所以我们就知道这个已经是到最后一个节点了，然后我们只需要改变指向

1. 递归调用过程

   • 初始调用：reverse1(head)，即 reverse1(A)。

   • 递归调用：reverse1(B)。

   • 递归调用：reverse1(C)。

   • 递归调用：reverse1(D)。

   • 当 D 的 Next 为 NULL 时，设置 head = D，并返回。

 我们可以知道在D的时候，Next已经为空，则这个时候就开始return了，然后我们就进入C，我们以C为例子来讲解

这个就是过程，改变下一个，本个为空

四，双向链表

struct Node {
	int data;
	Node* next;
	Node* prev;
};

双向链表是由两个地址域的

优点：如果我们由指向任意节点的指针，那么我们是方便反向查询的（仅需一个指针）

缺点：代码量增加，占用内存 

 双向链表的实现跟单向链表很像，只是多了一个地址域而已，这里就不过多解释了，对于堆的数据，我们链表一般都是在堆的，在堆里面查找数据一般都是利用指针

---

总结

我们目前基本学习完了链表的全部知识

-----增删改查

-----打印链表（迭代，递归）

-----反转链表（迭代，递归）

增删改查：这个就是要注意指向问题，比如增加到中间的位置的时候，是需要找到前面那个节点进程处理的

递归        ：需要注意的就是基准条件和过程，释放到入口的上面还是下面