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

在java中使用temp变量递归地反转链表。

在Java中使用temp变量递归地反转链表可以通过以下步骤实现:

  1. 定义一个链表节点类,包含一个值属性和一个指向下一个节点的指针属性。
代码语言:txt
复制
class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
    }
}
  1. 创建一个递归函数reverseList,接收一个链表头节点作为参数,并返回反转后的链表头节点。
代码语言:txt
复制
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode temp = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    
    return temp;
}
  1. 在主函数中创建一个链表,并调用reverseList函数进行链表反转。
代码语言:txt
复制
public static void main(String[] args) {
    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);
    
    ListNode reversedHead = reverseList(head);
    
    // 输出反转后的链表
    while (reversedHead != null) {
        System.out.print(reversedHead.val + " ");
        reversedHead = reversedHead.next;
    }
}

以上代码实现了在Java中使用temp变量递归地反转链表。在这个例子中,我们定义了一个链表节点类ListNode,然后使用递归函数reverseList来反转链表。在递归函数中,我们首先判断链表是否为空或只有一个节点,如果是,则直接返回该节点。否则,我们递归调用reverseList函数来反转链表的子链表,并将子链表的尾节点的下一个节点指向当前节点,然后将当前节点的下一个节点设为null,最后返回反转后的链表头节点。

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

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

相关·内容

【刷题】牛客— NC21 链表内指定区间反转

思路一(暴力破解版) 首先找到第 m-1 个节点并记录 然后开始反转 遍历 m - n 链表节点 ,并依次头插到一个新链表 m-1节点 指向新链表 ,新链表尾指向 n+1 个节点 完成反转。...该版本使用了一个十分巧妙的算法,不用额外开辟空间就能完成链表反转。...,反转区间的起点往后就是一个子问题,我们可以使用递归处理: 终止条件: 当m == 1,就可以直接反转前n个元素。...返回值: 将已经反转后的子问题头节点返回给上一级。 本级任务: 递归缩短区间,拼接本级节点与子问题已经反转的部分。...按照第二个递归的思路缩短终点的子问题,从第n个位置开始反转反转过程每个子问题作为反转后的尾,都要指向temp

8710

递归函数因不正确使用公共变量而形成死循环

昨天碰到了挺郁闷的错误,我写的一个递归函数,形成了死循环。...代码如下: '递归删除频道,参数:频道ID Sub DeleteBoard(bid)     '删除该频道所有新闻     News.DeleteByCondition "BoardID=" & bid...DeleteBoard bs(i).ID         Next     End If     '删除该频道     Board.Delete bid End Sub 后来检查才发现,罪魁祸首就是那个i,它是一个全局变量...递归的时候,另一次调用的时候,会修改它的值……因而,就莫明其妙的形成了死循环。...DeleteBoard bs(i).ID         Next     End If     '删除该频道     Board.Delete bid End Sub 增加了i的内部声明,这样,就会使用内部的

3.4K50

每日一题《剑指offer》链表篇之从尾到头打印链表

如输入{1,2,3}的链表如下图: 返回一个数组为[3,2,1] 数据范围 0 <= 链表长度 <= 10000 举例 解题思路 方法一:递归(推荐使用) 我们都知道链表无法逆序访问,那肯定无法直接遍历链表得到从尾到头的逆序结果...本级任务: 每级子任务递归进入下一级,等下一级的子问题输出数组返回时,将自己的节点值添加在数组末尾。 具体做法: step 1:从表头开始往后递归进入每一个节点。...方法二:递归 从上述方法一,我们可以看到每当我们反转链表的一个节点以后,要遍历进入下一个节点进入反转,相当于对后续的子链表进行反转,这可以看成是一个子问题,因此我们也可以使用递归,其三段式模版为: 终止条件...,因此也可以使用递归: 终止条件: 当一个链表已经因为递归到了末尾,另一个链表剩余部分一定都大于前面的,因此我们可以将另一个链表剩余部分拼在结果后面,结束递归。...step 2:递归回来的结果我们要加在当前较小值的节点后面,相当于不断较小值后面添加节点。 step 3:递归的终止是两个链表有一个为空。

13010

常见编程模式之就地反转链表

就地反转链表(In-place Reversal of a LinkedList) 基本原理及应用场景 很多问题中,我们需要对一个链表的节点连接进行反转,且通常需要原地进行,即不能使用额外的存储空间...这时我们可以使用就地反转链表模式,该模式本质上是一种迭代解法,流程如下图所示。首先设置一个变量 current 指向链表头部,以及另一个变量 previous 指向当前处理节点的前一个节点。...反转链表 II(Medium) 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 1 ≤ m ≤ n ≤ 链表长度。...「示例」: 给你这个链表:1->2->3->4->5: 当 k = 2 时,应当返回: 2->1->4->3->5 当 k = 3 时,应当返回: 3->2->1->4->5 这道题同样可以使用就地反转链表模式...,我们需要构建一个反转链表的函数,然后遍历目标链表,达到 k 个则进行反转,并将其拼接回主链表

64920

小白学算法-数据结构和算法教程: 反转链表

反转链表链表反转 给定一个指向链表头节点的指针,任务是反转链表。我们需要通过更改节点之间的链接来反转列表。...辅助空间: O(1) 使用递归反转链表: 这个想法是使用递归到达链表的最后一个节点,然后开始反转链表。 插图: 请按照以下步骤解决问题: 将链表分为两部分——第一个节点和链表的其余部分。...将头指针修复为 NULL 下面是上述方法的实现: """使用递归方法反转链接表的 Python3 程序 使用递归方法""" # 链接列表节点 class Node: def __init__(self...、current和next,递归访问每个节点并使用这三个指针建立链接。...辅助空间: O(N),函数调用栈空间 使用Stack反转链表: 这个想法是将所有节点存储堆栈,然后创建一个反向链表。 请按照以下步骤解决问题: 将节点(值和地址)存储堆栈,直到输入所有值。

16420

剑指Offer题解 - Day02

辅助栈法 首先,链表的特点是「从前到后」依次访问节点,而题目的要求是「倒序输出」节点,考虑使用后进先出的辅助栈进行解题。 思路:依次将链表节点放入辅助栈(数组)。...反转链表」 力扣题目链接[2] 定义一个函数,输入一个链表的头节点,反转链表并输出反转链表的头节点。...let pre = null; // pre指针指向链表尾部 let temp = null; // 初始化临时存储变量 while(cur) { // 遍历链表...解析:通过引入临时变量和pre变量,达到了改变next指向的效果。临时变量交换变量时进行使用,此处同理。...递归 本题也可以使用递归进行处理,通过回溯来修改next指向。 使用递归进行解题,一定要写递归的终止条件,否则会造成死循环导致内存溢出。

21810

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

反转链表并输出反转链表的头节点。...= temp; // 将正向链表头指针替换为暂存的节点,正向链表处理完成,开始下一轮处理 } return pre; }; 复杂度分析 时间复杂度 O(N):遍历链表使用线性大小时间。...空间复杂度 O(1):变量 pre 和 cur 使用常数大小额外空间。...解法二:递归 在线链接 当使用递归链表进行处理时,从链表的第一个节点出发,然后找到最后一个节点,该节点就是反转链表的头结点,然后进行回溯处理。 初始链表的头结点,head 标识。...定义 reverseHead 节点,保存反转链表值。 每次让 head 下一个节点的 next 指向 head,形成反转递归处理到最后一个节点,返回 reverseHead。

53700

搞定大厂算法面试之leetcode精讲15.链表

: 遍历链表,准备prev,curr,next三个指针,遍历的过程,让当前指针curr.next指向前一个指针prev,然后不断让prev,curr,next向后移动,直到curr为null 复杂度分析...反转链表 II(medium) 方法1 动画过大,点击查看 思路:切断left到right的子链,然后反转,最后反向连接 复杂度:时间复杂度O(n),空间复杂度O(1) js: var reverseBetween...pre; pre = cur; cur = next; } } } 方法2 动画过大,点击查看 思路:从left遍历到right,遍历的过程反转链表...两两交换链表的节点 (medium) 方法1.递归: ds_17 思路:用递归函数不断传入链表的下一个节点,终止条件是head === null|| head.next === null,也就是至少存在两个节点进行两两交换...,最后一层的时候开始两两反转,让当前递归层的head.next指向交换后返回的头节点,然后让反转后的新的头节点指向当前层的head的节点,这样就实现了两两交换,最后返回反转链表的头节点 复杂的分析:

38940

Java实现单向链表

(算法这方面我还是薄弱啊..脑子不够用了…..)写了两天就写了这么点东西… 操作一个链表只需要知道它的头指针就可以做任何操作了 添加数据到链表 遍历找到尾节点,插入即可(只要while(temp.next...首先判断该位置是否有效(链表长度的范围内) 找到想要插入位置的上一个节点 ?...获取链表的长度 每访问一次节点,变量++操作即可 删除给定位置的节点 将原本由上一个节点的指向后面一个节点 首先判断该位置是否有效(链表长度的范围内) 找到想要插入位置的上一个节点 ?...对链表进行排序 使用冒泡算法对其进行排序 找到链表倒数第k个节点 设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点 删除链表重复数据 操作跟冒泡排序差不多...反转链表递归和非递归两种方式,我觉得是挺难的。

2.5K103

Swift 反转链表 - LeetCode

LeetCode 题目: 反转链表 反转一个单链表。...示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归反转链表。你能否用两种方法解决这道题?...方案一: 迭代:链表第一个和第二个元素断开链表,保存后半段,前半段拼在新head前方,然后赋值给新head:具体如下面示意 p: a -> b -> c -> d -> e -> nil newHead...而newhead 的值没有发生改变,为该链表的最后一个结点,所以,反转后,我们可以得到新链表的head。 1、找到最后一个节点 递归找到newHead 2、反转最后一个节点head?....next = nil 断链 4、递归结束 递归结束,完成反转链表 代码二: /** * Definition for singly-linked list.

1.2K20

面试现场如何实现链表的逆序?

由于单链表与数组不相同,单链表每个节点的地址都存储在其前驱节点的指针域中,因此,对单链表任何一个结点的访问只能从链表的头指针开始进行遍历。...在对链表的操作过程,需要特别注意在修改结点指针域的时候,记录下后继结点的地址,否则会丢失后继结点。 方法一:就地逆序 序主要思路:遍历链表时,修改当前结点的指针域的指向,让其指向它的前驱结点。...为此,需要用一个指针变量来保存前驱结点的地址。此外,为了调整当前结点指针域的指向后还能找到后继结点,还需要另外一个指针变量来保存后继结点的地址,在所有的结点都被保存好以后就可以直接完成指针的逆序了。...其中,N为链表的长度。与方法一相比,这种方法不需要保存前驱结点的地址,与方法二相比,这种方法不需要递归调用,效率更高。 引申 ①对不带头结点的单链表进行逆序; ②从尾到头输出链表。...同理,对于链表2→3→4→5→6→7,也是先输出3→4→5→6→7,接着输出2,直到遍历到链表的最后一个结点7的时候会输出结点7,然后递归输出6,5,…,1。

1.1K41

数据结构04 链表的面试题

这篇文章包含的链表面试题如下: 1、从尾到头打印单向链表 2、查找单向链表的倒数第k个节点 3、反转一个单向链表【出现频率较高】 4、合并两个有序的单向链表,合并之后的链表依然有序【出现频率较高】 5...因此这一题要么自己新建一个栈,要么使用系统的栈(系统递归调用方法时的栈)。...方法2:使用系统的栈(递归 QuestionOneDemo.java 添加方法2 /** * 从尾到头打印单向链表 * 方法2:自己新建一个栈 *...代码: QuestionTwoDemo.java 添加方法 /** * 查找链表的倒数第k个节点的方法2 * * @param myLinkedList 需要查找的链表作为参数传递进来...如此类推,temp链表1和链表2之间移动,选出较小的节点,放到新链表的后面。

83560

《剑指offer》– 链表倒数第k个节点、反转链表、合并两个排序的链表

一、链表倒数时第k个节点: 1、题目: 输入一个链表,输出该链表倒数第k个结点。 2、解题思路:单链表具有单向移动的特性。...: 参考博客:https://www.jianshu.com/p/e385d9c06672 1、题目: 输入一个链表反转链表后,输出新链表的表头。...2、解题思路: 2-1:第一种:使用递归方式: (1)解题思路: 假设链表为[1,2,3,4,5]先迭代到链表末尾5,然后从5开始依次反转整个链表。...如下图所示,先迭代待最后一位5,并且设置一个新的节点newList作为反转链表的头结点,由于整个链表反转后的头就是最后一个数,所以newList存放的一直是反转后的头结点的地址,将head指向的地址赋值给...如果不是,则对链表进行迭代,然后给一个临时变量temp存储head.next,然后改变head.next的指向newList,然后把head赋值给newList,接着让head等于临时变量temp,就这样一直迭代完整个链表

35830

码不停题:LeetCode 75-Day3【链表

要小,将中间变量的下一节点指向list,则list1 指向list1的下一节点 如果其中一个为空,中间变量则指向另一个节点,继续遍历 代码实现 思路1代码实现 class Solution {...需要遍历链表一次。 空间复杂度:O(1)。 思路2复杂度 时间复杂度:O(n),其中 n 是链表的长度。需要对链表的每个节点进行反转操作。 空间复杂度:O(n),其中 n是链表的长度。...空间复杂度主要取决于递归调用的栈空间,最多为 n层 6、206. 反转链表 ❓题目描述 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。...思路2解析 链表的每一个节点push进栈,然后依次弹出pop()组成新的链表 思路3解析 递归遍历当前节点的下一节点,然后把下一节点的下一节点复制给当前节点,当前节点的下一节点指向null 代码实现...思路3复杂度分析 时间复杂度:O(n),其中 n 是链表的长度。需要对链表的每个节点进行反转操作。 空间复杂度:O(n),其中 n是链表的长度。

12520

【算法题解】 Day3 链表

[0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列   方法一:递归 思路 根据题意,给出了两个链表,需要将这俩链表合成一个按升序排列的链表,那么可以递归定义两个链表里的...如果 l1 或者 l2 一开始就是空链表 ,那么没有任何操作需要合并,所以我们只需要返回非空链表。否则,我们要判断 l1 和 l2 哪一个链表的头节点的值更小,然后递归决定下一个添加到结果里的节点。...反转链表 题目 206. 反转链表 难度:easy 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。... [0, 5000] -5000 <= Node.val <= 5000 方法一:栈 思路 看到反转的问题,最简单的就是通过开辟额外的空间来降低难度,这里我们可以使用栈,先顺序遍历将链表的节点都压入栈...关键是初始化的地方,可能有的同学会不理解, 可以看到双指针法初始化 cur = head,pre = null,递归初始化的逻辑是一样的,只不过写法变了。

13130
领券