LeetCode_LinkedList_92. Reverse Linked List II 反转链表 II(C++/Java)【递归】
2021/7/1 11:51:17
本文主要是介绍LeetCode_LinkedList_92. Reverse Linked List II 反转链表 II(C++/Java)【递归】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
一,题目描述
英文描述
中文描述
二,解题思路
三,AC代码
C++
Java
四,解题过程
第一博
一,题目描述
英文描述
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Example 1:
Example 2:
Constraints:
The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
Follow up: Could you do it in one pass?
中文描述
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
示例 1:
示例 2:
提示:
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二,解题思路
先考虑一个问题:反转链表前N个节点如何实现
- 一种方法是采用头插法(迭代),记录插入头部的节点个数,达到N时停止。此外还需要记录两个位置:头节点、下一个需要插入头节点之后的节点。(由于是在原链表进行操作,对于节点的剥离和重新插入要格外小心,一定要保证链表整体的唯一指向性原则)
- 一种是递归的方法,只需要保证反转节点的个数为N即可。
从上面可以看出递归方法实现起来更加简便,基本不需要添加其他东西,虽然递归的实现会在内存消耗上表现差一点。(需要不停将变量压入堆栈)
现在有了反转前N个节点的方法,那么接下来只需要定位头节点,然后调用反转N个节点的算法即可。
由于可能从头节点对链表进行反转,所以需要添加虚拟头节点。
哪种情况需要添加虚拟头节点?
一个简单的技巧,头节点可能发生变动时,可以添加虚拟头节点来简化算法,来保证始终有一个稳定的开头,从而避免各种可能的边界问题。比如在可能头部进行插入、删除等等。
三,AC代码
这里只给出递归算法的具体代码实现。
C++
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* ReverseN(ListNode* head, int n) { if(n == 0 || n == 1) return head; ListNode* tail = head->next, * h = ReverseN(head->next, n - 1); head->next = tail->next; tail->next = head; return h; } ListNode* reverseBetween(ListNode* head, int left, int right) { int cnt = right - left + 1; ListNode* h = new ListNode, * tem = h; h->next = head; while(--left) tem = tem->next; tem->next = ReverseN(tem->next, cnt); return h->next; } };
Java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseN(ListNode head, int n) { if(n == 0 || n == 1) return head; ListNode tail = head.next; ListNode h = reverseN(head.next, n - 1); head.next = tail.next; tail.next = head; return h; } public ListNode reverseBetween(ListNode head, int left, int right) { int cnt = right - left + 1; ListNode h = new ListNode(); h.next = head; ListNode tem = h; while(--left > 0) tem = tem.next; tem.next = reverseN(tem.next, cnt); return h.next; } }
四,解题过程
第一博
了解算法后就很好解决了,一发入魂
这篇关于LeetCode_LinkedList_92. Reverse Linked List II 反转链表 II(C++/Java)【递归】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现