首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

尝试使用递归和指向指针的指针反转链表,但reversell函数未给出预期的正确输出

链表反转是一个常见的算法问题,可以使用递归和指向指针的指针来实现。下面是一个示例的链表反转函数:

代码语言:txt
复制
#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

void reverseList(ListNode** head) {
    if (*head == nullptr || (*head)->next == nullptr) {
        return;
    }
    
    ListNode* prev = nullptr;
    ListNode* curr = *head;
    ListNode* next = nullptr;
    
    while (curr != nullptr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    *head = prev;
}

void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != nullptr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    std::cout << "Original List: ";
    printList(head);
    
    reverseList(&head);
    
    std::cout << "Reversed List: ";
    printList(head);
    
    return 0;
}

这段代码定义了一个链表节点结构ListNode,并实现了reverseList函数来反转链表。reverseList函数使用三个指针prevcurrnext来进行链表节点的反转操作。最后,通过调用printList函数来打印出反转后的链表。

这个算法的时间复杂度是O(n),其中n是链表的长度。

在腾讯云中,可以使用云服务器(CVM)来进行开发和运行这段代码。云服务器提供了强大的计算能力和灵活的配置选项,适用于各种应用场景。您可以通过以下链接了解更多关于腾讯云云服务器的信息:

请注意,以上答案仅供参考,具体的实现方式和推荐的产品可能因实际需求和环境而异。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

题型篇 | 数据结构与算法之链表系列

▉ 算法思路 通过上边问题分析,得出以下几种解决方法: ● 反转链表法 ● 栈实现 ● 递归实现 1、反转链表实现 从尾到头输出链表内容,一般思路就是将链表反转过来,然后从头到尾输出数据。...3、递归实现 可以通过递归方式来实现单链表从尾到头依次输出递归过程涉及到“递”“归”,反转链表输出数据,正式利用了循环“递”过程,所以数据先从头部输出,那么递归采用是“归”过程来输出内容,输出当前结点先要输出当前节点下一节点...) 17 // 2、判断链表是否可反转(头节点是否为空、是否有第二个结点) 18 // 3、尾指针指向第一个结点 next 19 // 4、尾指针向前移动 20 // 5、当前指针...1、结构上 存储链表内存空间是不连续,所有需要使用指针将这些零碎内存空间连接起来,导致需要通过指针来进行操作,这也是为什么链表中大多数都是关于指针操作原因。...如:从尾到头打印链表、合并两个有序链表反转链表等。 双指针链表中大部分都是进行指针操作,链表属于线性表结构(形如一条线结构),很多问题可以使用指针来解决,也是非常常用到

60510

前端学数据结构与算法(四):理解递归及拿力扣链表题目练手

再解决链表问题时,如果没有思路,可以用纸笔把指针指向过程画下来,然后再尝试从里面找到重复子问题会很有帮助。 206....反转链表反转一个单链表 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 上一章使用循环,这次尝试使用递归解决。因为是链表,所以思路是改变指针指向。...输入: 1->1->2 输出: 1->2 输入: 1->1->2->3->3 输出: 1->2->3 有了链表反转技巧后,再解这个题目就很容易了,还是递归到底,因为我们知道倒数一个节点倒数第二个节点...这个相对简单,再理解了反转后,使用之前递归调试法去理解相信一点都不难,就不画图了。...如果尝试用纸笔画出过程,就很容易发现子问题,让第一个节点指向第二个节点之后已经交换好链表,然后让第二个节点指向之前节点。

58300
  • 剑指Offer题解 - Day02

    示例 1: 输入:head = [1,3,2] 输出:[2,3,1] 限制: 0 <= 链表长度 <= 10000 思路: 尝试使用暴力法进行破解。...辅助栈法 首先,链表特点是「从前到后」依次访问节点,而题目的要求是「倒序输出」节点,考虑使用后进先出辅助栈进行解题。 思路:依次将链表节点放入辅助栈(数组)中。...反转链表」 力扣题目链接[2] 定义一个函数,输入一个链表头节点,反转链表输出反转链表头节点。...解析:通过引入临时变量pre变量,达到了改变next指向效果。临时变量也在交换变量时进行使用,此处同理。...核心思路就是先暂存当前节点next 指向,然后改变next指向为pre,然后将precur后移一位。 递归 本题也可以使用递归进行处理,通过回溯来修改next指向

    23710

    七十、反转和合并链表链表有环判断

    「---- Runsen」 ❞ 最近在重新梳理学算法知识,本文为链表常见操作复习总结文章,会讲解常见链表题目实现思路及附上答案,这些题目在leetcode上对应题号也有给出,好好学习算法吧~ 单链表反转...反转一个单链表需要当前节点next指针指向上一个结点pre,当前节点指针指向下一个结点,上一个结点指针指向当前节点。 通过迭代,依次反转结点指向。...其实,这道题考是「快慢指针」 O(1) 空间复杂度 通过使用具有 不同速度 快、慢两个指针遍历链表,空间复杂度可以被降低至 O(1) 。慢指针每次移动一步,而快指针每次移动两步。...这个解决方法使用递归,如果L1为空就返回L2,L2为空返回L1,L1val<=L2val,那么继续递归。...<=L2val,那么继续递归 #当前L1next指向一个递归函数 #意思是L1下一个L2哪个大,就作为当前L1next elif l1.val<=l2.val: l1.next

    46020

    备战蓝桥杯————递归反转链表一部分

    一、反转链表Ⅱ 题目描述         给你单链表指针 head 两个整数 left  right ,其中 left <= right 。...解题思路及代码  reverseN 递归反转链表算法,具体思路如下:         函数 reverseN 用于反转以 head 为起点前 n 个节点,并返回反转新头结点。         ...在反转过程中,将 head 下一个节点 head.next next 指针指向 head,实现反转。         ...将 head next 指针指向记录后驱节点 successor,保证反转链表与后面的节点连接起来。         返回新头结点 last,作为上一层递归结果。         ...通过不断地将头结点向后移动,并调整范围,我们可以确保在链表正确地定位到需要反转范围,并对其进行处理。这样,无论 m 值是多少,我们都能在链表正确地找到需要反转区间。

    12410

    【算法题解】 Day18 链表

    反转链表 题目 剑指 Offer 24. 反转链表 难度:easy 定义一个函数,输入一个链表头节点,反转链表输出反转链表头节点。...在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表任意节点或者 null。...对于当前节点,我们首先要进行拷贝,然后我们进行「当前节点后继节点」「当前节点随机指针指向节点」拷贝,拷贝完成后将创建新节点指针返回,即可完成当前节点指针赋值。...具体地,我们用哈希表记录每一个节点对应新节点创建情况。遍历该链表过程中,我们检查「当前节点后继节点」「当前节点随机指针指向节点」创建情况。...注意一个节点可能被多个其他节点指向,因此我们可能递归地多次尝试拷贝某个节点,为了防止重复拷贝,我们需要首先检查当前节点是否被拷贝过,如果已经拷贝过,我们可以直接从哈希表中取出拷贝后节点指针并返回即可

    15320

    【数据结构算法】删除链表中间节点

    指针法: 使用两个指针,一个快速指针 fast 一个慢指针 slow。开始时,fast slow 都指向链表头部。...选择合适算法:根据问题具体要求,选择合适算法。例如,如果需要找到链表长度,可以使用快慢指针法;如果需要插入或删除节点,可以使用指针法;如果需要反转链表,可以使用迭代或递归方法。...在实现代码时,需要注意指针操作,确保指针正确指向。例如,在插入节点时,需要更新新节点和它后面节点指针;在删除节点时,需要更新被删除节点前一个节点指针,使其指向被删除节点下一个节点。...测试验证:运行代码,测试算法正确效率。如果发现问题,需要对代码进行调试修改。你可以使用一些测试用例来验证算法正确性,例如测试空链表、只有一个节点链表、有两个节点链表等。...例如,可以使用哈希表来存储每个节点对应节点指针,以便快速查找节点;可以使用迭代方法来遍历链表,避免使用递归方法导致栈溢出问题。

    12010

    Java实现单向链表

    ,将两种(双向/单向)链表最后一个结点指向第一个结点从而实现循环 操作链表要时刻记住是: 节点中指针指向就是一个节点了!...反转链表参考自: http://www.cnblogs.com/hanxue112253/p/8533426.html 四、最后 理解链表本身并不难,做相关操作就弄得头疼,head.next next...= null),退出循环就会找到尾节点) 遍历链表 从首节点(有效节点)开始,只要不为null,就输出 给定位置插入节点到链表中 将原本由上一个节点指向交由插入节点来指向 上一个节点指针指向想要插入节点...,只要它相等,就能删除了~ 查询链表中间节点 这个算法也挺有趣:一个每次走1步,一个每次走两步,走两步遍历完,然后走一步指针,那就是中间节点 递归从尾到头输出链表 只要下面还有数据,那就往下找...反转链表递归递归两种方式,我觉得是挺难

    2.6K103

    如何高效判断回文单链表

    2->2->1->null 输出: true 这道题难点在于,单链表无法倒着遍历,无法使用指针技巧。...那么最简单办法就是,把原始链表反转存入一条新链表,然后比较这两条链表是否相同。关于如何反转链表,可以参见前文 递归思维:k 个一组反转链表。...实际上就是把链表节点放入一个栈,然后再拿出来,这时候元素顺序就是反,只不过我们利用递归函数堆栈而已。 当然,无论造一条反转链表还是利用后续遍历,算法时间空间复杂度都是 O(N)。...= null) { slow = slow.next; fast = fast.next.next; } // slow 指针现在指向链表中点 2、如果fast指针没有指向null,说明链表长度为奇数...其实这个问题很好解决,关键在于得到p, q这两个指针位置: 这样,只要在函数 return 之前加一段代码即可恢复原先链表顺序: p.next = reverse(q); 篇幅所限,我就不写了,读者可以自己尝试一下

    90110

    如何判断回文链表

    true */ 这道题关键在于,单链表无法倒着遍历,无法使用指针技巧。...那么最简单办法就是,把原始链表反转存入一条新链表,然后比较这两条链表是否相同。关于如何反转链表,可以参见前文「递归操作链表」。...实际上就是把链表节点放入一个栈,然后再拿出来,这时候元素顺序就是反,只不过我们利用递归函数堆栈而已。 ? 当然,无论造一条反转链表还是利用后序遍历,算法时间空间复杂度都是 O(N)。...2、如果fast指针没有指向null,说明链表长度为奇数,slow还要再前进一步: if fast != nil{ slow = slow.next } ?...算法总体时间复杂度 O(N),空间复杂度 O(1),已经是最优了。 我知道肯定有读者会问:这种解法虽然高效,破坏了输入链表原始结构,能不能避免这个瑕疵呢?

    88820

    LeetCode | 206.反转链表

    上面的题就是 反转链表 题目的截图,同时 LeetCode 给出了一个函数定义,然后要求实现反转链表函数体。...参数 head 指向链表 1 结点,只要我们循环遍历整个链表,并且让当前结点指针指向前一个结点即可。...但是,这样就会有另外一个问题,当前元素指针指向下一个元素,如果将当前元素指针指向了上一个元素,那么当前元素下一个元素就断链了,也就是无法找到当前元素下一个元素了。...在写完 reverseList 函数体后,点击右下角 “执行代码”,然后观察 “输出预期结果” 是否一致,一致的话就点击 “提交” 按钮。...点击 “提交” 按钮后,系统会使用更多测试用例来测试我们写函数体,如果所有的测试用例都通过了,那么就会给出 “通过” 字样,如果没有通过,会给出失败那一组测试用例,我们继续修改代码。

    31030

    剑指offer No.15 反转链表

    一、题目描述 输入一个链表反转链表后,输出链表表头。...示例1 输入: {1,2,3} 返回值: {3,2,1} 二、解题思路 思路一:递归 /* struct ListNode { int val; struct ListNode *next; ListNode...1)pre指针指向已经反转链表最后一个节点,最开始没有反转,所以指向nullptr 2)current指针指向反转链表第一个节点,最开始第一个节点待反转,所以指向head 3)nextnode...指针指向反转链表第二个节点,目的是保存链表,因为cur改变指向后,后面的链表则失效了,所以需要保存 接下来,循环执行以下三个操作 1)nextnode = current->next, 保存作用...2)current->next = pre 反转链表第一个节点下个指针指向反转链表最后一个节点 3)pre = current, current = nextnode; 指针后移,操作下一个反转链表第一个节点

    14920

    反转链表

    一、题目 定义一个函数,输入一个链表头节点,反转链表输出反转链表头节点。...二、示例 示例: 【输入】 1->2->3->4->5->NULL 【输出】 5->4->3->2->1->NULL 限制: • 0 <= 节点个数 <= 5000 三、解题思路 本题给出数据结构是单向链表...那么既然是单向链表,我们遍历链表中所有结点时候,就只能通过调用ListNode.next方式逐一向后遍历节点,遍历方式当然不是问题难点,难点是如何进行翻转呢?...【操作2】在递归遍历操作之后,执行head.next.next = head;将当前节点head下一个节点next后置指针指向head,这样就实现了反转;但是,此处需要注意是,我们还需要将head.next...设置为null,因为这个对于原链表头节点很重要(因为它变为了新链表尾节点,其next指针应该被设置为null) 解题思路说完了,我们举例,尝试将Node(1)——>Node(2)——>Node(3)

    13420

    前端最高频算法题之一:反转链表

    ,输入一个链表头节点,反转链表输出反转链表头节点。...示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 解法一:迭代(双指针) 在线链接 本方法是对链表进行遍历,然后在访问各节点时修改 next 指向...初始化 cur pre 两个节点,分别指向 head null。 对链表进行循环,声明 temp 节点用来保存当前节点下一个节点。...解法二:递归 在线链接 当使用递归链表进行处理时,从链表第一个节点出发,然后找到最后一个节点,该节点就是反转链表头结点,然后进行回溯处理。 初始链表头结点,head 标识。...定义 reverseHead 节点,保存反转链表值。 每次让 head 下一个节点 next 指向 head,形成反转递归处理到最后一个节点,返回 reverseHead。

    56500

    剑指offer | 面试题18:反转链表

    反转链表 题目描述:定义一个函数,输入一个链表头节点,反转链表输出反转链表头节点。...有迭代(双指针)、递归两种实现方法。 方法一:迭代(双指针) 考虑遍历链表,并在访问各节点时修改 next 引用指向,算法流程见注释。...考虑使用递归法遍历链表,当越过尾节点后终止递归,在回溯时修改各节点 next 引用指向。...recur(cur, pre) 递归函数: 终止条件:当 cur 为空,则返回尾节点 pre (即反转链表头节点); 递归后继节点,记录返回值(即反转链表头节点)为 res ; 修改当前节点 cur...引用指向前驱节点 pre ; 返回反转链表头节点 res ; reverseList(head) 函数: 调用并返回 recur(head, null) 。

    46010

    Leetcode链表题目总结

    奇偶链表 题目描述   给定一个单链表,把所有的奇数节点偶数节点分别排在一起。请注意,这里奇数节点偶数节点指的是节点编号奇偶性,而不是节点奇偶性。   请尝试使用原地算法完成。...题目描述   定义一个函数,输入一个链表头节点,反转链表输出反转链表头节点。   ...所以,在遍历链表时我们要逐个修改链表指针指向。这个题目也可以用递归来做,一直递归链表最后一个结点,该结点就是反转头结点,记作head .   ...此后,每次函数在返回过程中,让当前结点下一个结点 next 指针指向当前节点。同时让当前结点 next 指针指向 NULL ,从而实现从链表尾部开始局部反转。...当递归函数全部出栈后,链表反转完成。

    57620

    【Leetcode】单链表常见题

    cur初始化为指向头节点head,而prev初始化为NULL 在这个删除链表中指定值节点函数中,prev指针被初始化为NULL是出于以下几个原因: 表示头节点之前:链表头节点之前没有节点,所以在遍历开始之前...这个算法分为两个主要阶段: 确定链表中是否存在环: 使用两个指针,slowfast,它们初始时都指向链表头节点head。然后,slow每次向前移动一个节点,而fast每次向前移动两个节点。...在这一步中,恢复原始链表next指针,并将复制链表next指针指向正确节点 所以这道题只是逻辑复杂一点,并没有很难理解 8.反转链表 题目链接: 206.反转链表 题目描述: 方法一:迭代法...迭代法通过遍历链表,逐个改变节点指向来实现链表反转。...递归法利用递归回溯过程实现链表反转

    8810

    听说过两天反转链表又写不出来了?

    反转链表写法很简单,一些同学甚至可以背下来过一阵就忘了该咋写,主要是因为没有理解真正反转过程。...示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 思路 如果再定义一个新链表,实现链表元素反转,其实这是对内存空间浪费。...其实只需要改变链表next指针指向,直接将链表反转 ,而不用重新定义一个新链表,如图所示: ?...接下来,就是循环走如下代码逻辑了,继续移动precur指针。 最后,cur 指针已经指向了null,循环结束,链表反转完毕了。...= cur; cur = temp; } return pre; } }; 递归递归法相对抽象一些,但是其实指针法是一样逻辑,

    54820

    链表面试题(动图详解)-明明做出来了却为什么没有Offer?

    从尾到头打印链表 题目:输入一个链表头节点,从尾到头反过来打印每个节点值。 第一反应可能是把链表指针反转过来,然后从头到尾输出。...那么反转链表时,需要三个指针分别指向当前遍历节点、前驱节点、后继节点即可完成指针顺序交换。...k个节点 题目:输出单向链表倒数第k个节点 很自然想到先走到链表尾端,再从尾端回溯k步,单向链表明显是行不通。...还是使用指针来解决,设链表环有n个节点,则第一个指针先走n步,然后两个指针以相同速度前进,当第二个指针指向入口时,第一个指针已经绕着环走了一圈也到了入口处,两指针相遇。...另外面试官不给你Offer,可能是因为你开辟了另外内存空间存储合并后链表,而合并前链表空间释放等。直接使用递归修改指针方向即可。

    42630

    链表:听说过两天反转链表又写不出来了?

    关于代码一切尽在「代码随想录」 反转链表写法很简单,一些同学甚至可以背下来过一阵就忘了该咋写,主要是因为没有理解真正反转过程。 第206题:反转链表 题意:反转一个单链表。...示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 思路 如果再定义一个新链表,实现链表元素反转,其实这是对内存空间浪费。...其实只需要改变链表next指针指向,直接将链表反转 ,而不用重新定义一个新链表,如图所示: ?...接下来,就是循环走如下代码逻辑了,继续移动precur指针。 最后,cur 指针已经指向了null,循环结束,链表反转完毕了。...; 递归递归法相对抽象一些,但是其实指针法是一样逻辑,同样是当cur为空时候循环结束,不断将cur指向pre过程。

    36810
    领券