【链表OJ 2】反转链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【链表OJ 2】反转链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言:

🎈欢迎大家来到Dream_Chaser～的博客🎈

🚩本文收录于 C--数据结构刷题的专栏中 -->http://t.csdn.cn/n6UEP

首先欢迎大家的来访，其次如有错误，非常欢迎大家的指正,互相学习进步。

一.反转链表

来源:206. 反转链表 - 力扣（LeetCode）

题目:

【链表OJ 2】反转链表,C--数据结构刷题,链表,数据结构,c语言,开发语言,笔记,vscode

1.迭代法

思路:

首先，检查链表头节点是否为空。如果为空，表示链表为空，直接返回NULL。

定义三个指针变量：n1、n2和n3。初始时，n1指向NULL，n2指向头节点head，n3指向n2的下一个节点。

进入循环，条件是n2不为NULL。循环的目的是将当前节点n2的指针指向它的前一个节点n1，实现反转。

在循环内部，首先将n2的next指针指向n1，完成反转操作。

然后，更新n1、n2和n3的值。将n2赋值给n1，将n3赋值给n2，同时判断n3是否为NULL，如果不为NULL，则将n3更新为n3的下一个节点。

当循环结束时，所有节点都被反转了，n1指向原链表的最后一个节点，也就是反转后的链表的头节点。

返回n1，作为反转后的链表的头节点。

动图演示:

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = n2->next;
    while (n2)
    {
        n2->next = n1;

        n1 = n2;
        n2 = n3;
        if (n3)//加上这里的原因，当n2指向最后一个结点时.此时n3已经为NULL
            n3 = n3->next;//若对空指针解引用就会出现异常
    }
    return n1;
}

代码执行:

【链表OJ 2】反转链表,C--数据结构刷题,链表,数据结构,c语言,开发语言,笔记,vscode

注意:如果去掉条件if(n3)则会出现问题

原因:

if (n3) 加上此条件的原因，当n2指向最后一个结点时.此时n3已经为NULL
n3 = n3->next;//若对空指针解引用就会出现异常

执行:

【链表OJ 2】反转链表,C--数据结构刷题,链表,数据结构,c语言,开发语言,笔记,vscode

2.头插法

创建两个指针变量：cur和rhead。cur用于迭代遍历原始链表，rhead用于指向反转后的链表的头部。

进入while循环，循环条件为cur不为NULL，即还未遍历完原始链表。

在循环内部，首先创建一个指针变量next，用于保存cur的下一个节点的地址，以防止丢失。

执行头插操作，将cur节点插入到反转链表的头部。将cur的next指针指向rhead，实现插入操作。然后更新rhead，使其指向cur，将cur成为新的头部。

更新cur，使其指向next，继续迭代遍历原始链表的下一个节点。

循环结束后，原始链表遍历完毕，整个链表已经完成反转。返回rhead，即为反转后的链表的头部

动图演示:

struct ListNode* reverseList(struct ListNode* head) {
       struct ListNode* cur=head,*rhead=NULL;
      while(cur)
      {
      struct ListNode* next=cur->next;
     
      //头插
      cur->next=rhead;
      rhead=cur;
     //迭代
      cur=next;
      } 
      return rhead;
}

执行:

【链表OJ 2】反转链表,C--数据结构刷题,链表,数据结构,c语言,开发语言,笔记,vscode