【数据结构OJ题】反转链表

简介: 力扣题目——反转链表

1. 题目描述

02baf43bbd7165cee9f43390818f31cb.png

2. 思路分析

方法一:三指针翻转法

使用三个结构体指针n1,n2,n3,原地修改结点指向。

就是让n1先指向空指针NULL,n2指向头结点,n3指向头结点下一个结点

用n2进行遍历。然后让n1指向n2,n2指向n3,n3指向n3的下一个结点。如此循环遍历,直到n2指向空指针NULL时停止

最后返回n1即可。
image.png

这里为什么要用三个指针呢?

因为如果只用两个指针,那么我们让n1指向n2后,链表的连接就断了,找不到原链表n2的下一个结点了。

同时,我们需要注意一些临界条件特殊情况

比如链表是空的,我们就让最后返回空即可

一般情况至少有一个结点存在,所以我们得在n2不为空的情况下(即if(n2)),让n3指向n2的下一个结点。(n3=n2->next)

遍历过程中,n3要指向下一个结点,那么n3就不能是空指针(即if(n3) n3=n3->next)

方法二:头插法

对每一个结点都进行头插

3. 代码实现

方法一:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


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

image.png

方法二:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


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

image.png

相关文章
|
16天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
44 4
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
25 7
|
1月前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
16 0
数据结构与算法学习五:双链表的增、删、改、查
|
16天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
37 0
|
30天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
21 0
|
1月前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
1月前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
1月前
|
算法 Java
数据结构与算法学习六:单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例,详细讲解了约瑟夫环问题的解决方案,并提供了Java代码实现。
19 0