首页
学习
活动
专区
工具
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、结构上 存储链表的内存空间是不连续的,所有需要使用指针将这些零碎内存空间连接起来,导致需要通过指针来进行操作,这也是为什么链表中大多数都是关于指针的操作的原因。...如:从尾到头打印链表、合并两个有序链表、反转链表等。 双指针:链表中大部分都是进行指针操作,链表属于线性表结构(形如一条线的结构),很多问题可以使用双指针来解决,也是非常常用到的。

61110

剑指Offer题解 - Day02

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

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

    再解决链表问题时,如果没有思路,可以用纸和笔把指针指向的过程画下来,然后再尝试从里面找到重复子问题会很有帮助。 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 有了链表反转的技巧后,再解这个题目就很容易了,还是递归到底,因为我们知道倒数一个节点和倒数第二个节点...这个相对简单,再理解了反转后,使用之前的递归调试法去理解相信一点都不难,就不画图了。...如果尝试用纸和笔画出过程,就很容易发现子问题,让第一个节点指向第二个节点之后已经交换好的链表,然后让第二个节点指向之前的节点。

    59200

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

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

    46820

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

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

    12910

    【算法题解】 Day18 链表

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

    15520

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

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

    13810

    如何高效判断回文单链表?

    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); 篇幅所限,我就不写了,读者可以自己尝试一下

    91510

    Java实现单向链表

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

    2.6K103

    如何判断回文链表

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

    89720

    Python 实现反转、合并链表有啥用?

    反转链表先看在 Python 中实现反转链表,我们可以使用迭代和递归两种方法。下面分别给出这两种方法的详细实现。...迭代方法迭代方法的核心思想是遍历链表,在遍历过程中改变每个节点的指针方向,使其指向前一个节点。...: [5, 4, 3, 2, 1]递归方法递归方法的核心思想是先递归地反转当前节点之后的链表,然后将当前节点的指针指向前一个节点。...head # 递归地反转当前节点之后的链表 new_head = reverseList(head.next) # 将当前节点的下一个节点的指针指向当前节点 head.next.next...: [5, 4, 3, 2, 1]以上两种方法都可以实现链表的反转,迭代方法的时间复杂度是 $O(n)$,空间复杂度是 $O(1)$;递归方法的时间复杂度也是 $O(n)$,但空间复杂度是 $O(n)$

    3700

    LeetCode | 206.反转链表

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

    31330

    剑指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; 指针后移,操作下一个未反转链表的第一个节点

    15220

    反转链表

    一、题目 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。...二、示例 示例: 【输入】 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)

    13720

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

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

    56700

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

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

    48810

    Leetcode链表题目总结

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

    58320

    【Leetcode】单链表常见题

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

    10210

    前端算法系统练习: 链表篇完结

    主要分为下面这几个主题: 反转链表 反转链表这里一共有三个题目供大家训练。分别是原地单链表的反转、两个一组反转链表和K个一组反转链表,难度由阶梯式上升。...作为新手来说,很容易将当前节点的 next指针直接指向前一个节点,但其实当前节点下一个节点的指针也就丢失了。因此,需要在遍历的过程当中,先将下一个节点保存,然后再操作next指向。...请使用一趟扫描完成反转。 说明:1 ≤ m ≤ n ≤ 链表长度。...var reverseBetween = function(head, m, n) { // 递归反转函数 let reverse = (pre, cur) => { if(!...唯一的不同在于两个一组的情况下每一组只需要反转两个节点,而在 K 个一组的情况下对应的操作是将 K 个元素的链表进行反转。 递归解法 这一题我觉得递归的解法更容易理解,因此,先贴上递归方法的代码。

    35510

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

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

    37410
    领券