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

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

不带哨兵位结点

不带哨兵位结点的意思是头结点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;
}
目录
相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
69 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
29天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
32 4
|
1月前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
|
1月前
|
算法
经典算法之链表篇(二)
经典算法之链表篇(二)
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
5天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
14 1
|
7天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
10天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。