【链表OJ 2】反转链表

前言:

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

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

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

一.反转链表

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

题目:

1.迭代法

思路:

1. 首先，检查链表头节点是否为空。如果为空，表示链表为空，直接返回NULL。
   
2. 定义三个指针变量：n1、n2和n3。初始时，n1指向NULL，n2指向头节点head，n3指向n2的下一个节点。
   
3. 进入循环，条件是n2不为NULL。循环的目的是将当前节点n2的指针指向它的前一个节点n1，实现反转。
   
4. 在循环内部，首先将n2的next指针指向n1，完成反转操作。
   
5. 然后，更新n1、n2和n3的值。将n2赋值给n1，将n3赋值给n2，同时判断n3是否为NULL，如果不为NULL，则将n3更新为n3的下一个节点。
   
6. 当循环结束时，所有节点都被反转了，n1指向原链表的最后一个节点，也就是反转后的链表的头节点。
   
7. 返回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;
}

代码执行:

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

原因:

if (n3) 加上此条件的原因，当n2指向最后一个结点时.此时n3已经为NULL

  n3 = n3->next;//若对空指针解引用就会出现异常

执行:

2.头插法

1. 创建两个指针变量：cur和rhead。cur用于迭代遍历原始链表，rhead用于指向反转后的链表的头部。
   
2. 进入while循环，循环条件为cur不为NULL，即还未遍历完原始链表。
   
3. 在循环内部，首先创建一个指针变量next，用于保存cur的下一个节点的地址，以防止丢失。
   
4. 执行头插操作，将cur节点插入到反转链表的头部。将cur的next指针指向rhead，实现插入操作。然后更新rhead，使其指向cur，将cur成为新的头部。
   
5. 更新cur，使其指向next，继续迭代遍历原始链表的下一个节点。
   
6. 循环结束后，原始链表遍历完毕，整个链表已经完成反转。返回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;
}

执行:

  本文到此结束，如有错误，欢迎大家指正，感谢来访。🚩