数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)

简介: 数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)

不带哨兵位结点

不带哨兵位结点的意思是头结点head只是一个指向第一个结点的指针。带哨兵位结点时,则有一个表头结点,其数据域为NULL,指针域则指向第一个结点。

题目示例

示例 1

输入:head = [1,2,3,4,5]输出:[5,4,3,2,1]

示例2

输入:head = [1,2] 输出:[2,1]

示例3

输入:head = [] 输出:[]

题目思路

思路一

思路二

题目代码

思路一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
 
struct ListNode* reverseList(struct ListNode* head)
{
    if(head == NULL)
        return head;
 
    struct ListNode *note1,*note2,*note3;
    note1 = NULL;
    note2 = head;
    note3 = head->next;
 
    while(note2)
    {
        //翻转
        note2->next = note1;
 
        //迭代往后
        note1 = note2;
        note2 = note3;
        if(note3)
            note3 = note3->next;
    }
    return note1;
}

思路二

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

带有哨兵位结点

简单思路

带有哨兵位结点(带表头)的翻转也很简单,我们用思路二来写一下其中的一种解法。

先把头结点head用phead记录下来,把整个链表翻转之后,再用phead链接翻转之后的链表,返回phead即可。

代码

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode *phead = head;
    struct ListNode *cur = head;
    struct ListNode*newhead = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;
        //迭代往后
        cur = next;
    }
    phead->next = newhead;
    return phead;
}
目录
相关文章
|
5天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
5天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
6天前
|
存储 算法 搜索推荐
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念,通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中,理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
6 1
|
23天前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
|
23天前
|
算法
经典算法之链表篇(二)
经典算法之链表篇(二)
|
23天前
|
算法 索引
经典算法之链表篇
经典算法之链表篇
|
2天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
38 9
|
1天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
20 4
|
24天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
25 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
5天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!