单链表反转原理及实现

谁践踏了优雅 2023-06-23 13:26 8阅读 0赞

# 1 节点定义 #

单链表节点的数据结构定义如下：

/* 定义结节点 */
    typedef struct _Node
    {
    	int value;
    	Node* next;
    }Node;

# 2 方法：迭代法 #

## 2.1 思路 ##

遍历整个链表，并把当前节点的next指向上一节点。

## 2.2 分析 ##

1.初始链表状态如下图所示。

![20191219162740234.bmp][]

2.定义节点指针

①定义前向节点指针，并初始化为head。Node\* prev = head;

②定义当前节点指针，并指向head的下一节点。Node\* cur = head->next;

![20191219165055623.bmp][]

3.取其中一个节点进行分析，假如当前状态如下图所示：

①将当前节点的next（即下一节点地址）赋值给临时指针，此时临时指针指向下一节点；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2twZW5naw_size_16_color_FFFFFF_t_70][]

②将前向节点的指针prev赋值给当前节点指针的next，即当前节点的下一节点指向了前向节点；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2twZW5naw_size_16_color_FFFFFF_t_70 1][]

③将当前节点的指针cur赋值给前向节点指针prev。将临时指针temp赋值给当前指针cur。前向节点和当前节点都向前进了一步，指针移到到各自的下一节点；

![20191219162942442.bmp][]

4.循环执行第3步的过程，直到当前节点的next为NULL为止，此时的前向指针prev即为反转后链表的收地址。反转完成后的链表如下图所示：

![20191219163018586.bmp][]

#  3 代码实现 #

/* 单链表反转 */
    Node* reverseList(Node* head)
    {
    	Node* prev = head;
    	Node* cur = head->next;
    	head->next = NULL;
    	while (cur != NULL)
    	{
    		Node* temp = cur->next;//记录当前节点的下一个节点
    		cur->next = prev;//当前节点指向前向节点
    		//指针后移
    		prev = cur;
    		cur = temp;
    	}
    	return prev;
    }

[20191219162740234.bmp]: https://img-blog.csdnimg.cn/20191219162740234.bmp
[20191219165055623.bmp]: https://img-blog.csdnimg.cn/20191219165055623.bmp
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2twZW5naw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191219162841429.bmp?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2twZW5naw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2twZW5naw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191219162919411.bmp?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2twZW5naw==,size_16,color_FFFFFF,t_70
[20191219162942442.bmp]: https://img-blog.csdnimg.cn/20191219162942442.bmp
[20191219163018586.bmp]: https://img-blog.csdnimg.cn/20191219163018586.bmp