【数据结构与算法 经典例题】反转链表(图文详解)

               

            💓 博客主页：倔强的石头的CSDN主页 

             📝Gitee主页：倔强的石头的gitee主页

   ⏩ 文章专栏：《数据结构与算法 经典例题》C语言

                                  期待您的关注

​

目录

一、问题描述

二、解题思路分析

三、代码实现

---

一、问题描述

二、解题思路分析

通过三个指针n1,n2,n3来实现链表的反转

1.首先初始化 n1为空    n2指向head     n3指向head-＞next

 2.然后  让n2的next指针指向n1 完成第一步反转 

3. 接下来移动三个指针

n1指向n2

n2指向n3

n3指向n3的下一个节点

4.然后

让n2的next指针指向n1 完成反转 

5.循环执行反转和移动指针的过程 直到

n3指向空

n2指向最后一个节点

n1指向倒数第二个节点

6.此时再执行最后一次反转 最后一个节点的next指针指向倒数第二个节点

7.最后一次移动节点 

n1指向n2（最后一个节点）

n2指向n3（null）

n3此时已经为空，不能解引用

所以n3指针的移动，要加一个判空的条件

n2作为循环结束的条件

而循环结束时，n1刚好停留在原链表的尾节点，也就是新链表的首节点

三、代码实现

struct ListNode* reverseList(struct ListNode* head) 
{
    if (head == NULL)
	    return head;//对空链表做特殊处理
    else
    {
	    struct ListNode* n1, * n2, * n3;
        n1 = NULL;
        n2 = head;
        n3 = n2->next;
	    while (n2)//当n2指向空时，链表节点已经遍历完成，next指针修改完成
	    {
		    n2->next = n1;
		    n1 = n2;
		    n2 = n3;
		    if (n3)//对n3判空，防止对空指针解引用
			    n3 = n3->next;
	    }
	    return n1;//当循环结束时，n1是原链表的尾节点，反转后的首节点
    }    
}