目录
一,题目描述
英文描述
中文描述
二,解题思路
三,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个节点的算法即可。
由于可能从头节点对链表进行反转,所以需要添加虚拟头节点。
哪种情况需要添加虚拟头节点?
一个简单的技巧,头节点可能发生变动时,可以添加虚拟头节点来简化算法,来保证始终有一个稳定的开头,从而避免各种可能的边界问题。比如在可能头部进行插入、删除等等。
这里只给出递归算法的具体代码实现。
/** * 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; } };
/** * 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; } }
了解算法后就很好解决了,一发入魂