【链表OJ 2】反转链表

简介: 【链表OJ 2】反转链表

前言:

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

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

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


一.反转链表


来源:206. 反转链表 - 力扣(LeetCode)

题目:

ac452e99cfd64e05ae899995fe242cb4.png


1.迭代法

思路:

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


动图演示:

9b63d2ad569742f5b1b8d163ad861672.gif

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;
}

代码执行:

a82573b59e8b47df8a6be96cae497d3d.png

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

原因:

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

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


执行:

38325cdab1cc4c59bffbe1ab6bd808f0.png


2.头插法

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


动图演示:

051ffa80d8fc4f6da5d0b1e384a36d7c.gif

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;
}

执行:

a9f7c72898c044e8b9a1aee7776ac886.png

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

相关文章
|
1月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
4月前
【数据结构OJ题】环形链表
力扣题目——环形链表
37 3
【数据结构OJ题】环形链表
|
4月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
51 1
【数据结构OJ题】复制带随机指针的链表
|
4月前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
30 1
【数据结构OJ题】环形链表II
|
4月前
【数据结构OJ题】相交链表
力扣题目——相交链表
33 1
【数据结构OJ题】相交链表
|
4月前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
41 8
【数据结构OJ题】合并两个有序链表
|
4月前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
37 1
【数据结构OJ题】链表中倒数第k个结点
|
4月前
【数据结构OJ题】链表分割
牛客题目——链表分割
32 0
【数据结构OJ题】链表分割
|
4月前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
39 0
【数据结构OJ题】链表的回文结构
|
4月前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
25 0
【数据结构OJ题】链表的中间结点