博客

在实现反转之前，先回顾链表操作的一些重点。

现链表节点是以下形式：

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

解决链表问题一定要理解深刻，一些要注意的点：

链表中每一个节点都是物理内存中实际存在的，物理节点本身是固定不变的，给定了地址就在那个地址中不会转移、变化等，链表之所以能够添加，删除，反转等，本质是指向这些物理节点的指针节点在移动，即给物理节点赋予的指针是变化的，而我们进行链表操作实际上是操作这些指针节点。

拿一个例子做说明：假设已经建立一个链表,名为list,它也代表链表的头结点：

蓝色方框表示的是物理内存中实际存在的节点，我在方框下方标注了他们所处的内存地址（橙色）。我用名为list的指针（绿色方框）表示指向这片具有逻辑顺序关系的链表。

理解1：一旦链表已经形成，通过对头节点操作，可以索引出链表中所有的节点，并且是基于箭头所指方向进行索引的！也就是说只能说单向的，箭头的含义其实就在于这里-单向。拿这个链表再作解释：

通过

list = list->next

List所指向的节点到了值为2的物理内存上。这样以后，没有建立其他辅助节点指针的条件下，List就再也不具备能力回到值为1的那个物理节点上，这就是单向的意义。List继续可以往后索引。

那么对于链表反转，我们想要实现的就是从上面的链表形式转换成如下的形式，什么改变了，很明显，箭头反过来了。箭头变了，意味着next指向的地址也要反过来！

先给出实现代码：

Node* ReverseList(Node* list)
{
	Node* tmpNode = list;
	Node* preNode = nullptr;
	while (tmpNode)
	{
		Node* nextNode = tmpNode->next;
		tmpNode->next = preNode;
		preNode = tmpNode;
		tmpNode = nextNode;
	}
	list = preNode;
	return list;
}

一条一条语句分析：

Node* tmpNode = list;

增加一个辅助指针，也可以说辅助节点吧，为了方便，后面提的“节点”都表示为“指向节点的指针”，区分物理节点。

Node* preNode = nullptr;

进入循环中依次索引链表中的节点。

1：Node* nextNode = tmpNode->next;

2：tmpNode->next = preNode;

3-4：

preNode = tmpNode;

tmpNode = nextNode;

第二次：

Node* nextNode = tmpNode->next;

tmpNode->next = preNode;

此时发现，箭头反过来了，这正不是我们想要的，tmpNode和preNode继续往后推，

preNode = tmpNode;

tmpNode = nextNode;

现在要做的不就把tmpNode->next指向preNode不就完事了

Node* nextNode = tmpNode->next;

tmpNode->next = preNode;

到这里基本上结束了，把preNode赋给list,完成。