LeetCode92. ๅ่ฝฌ้พ่กจ II๐๐๐ไธญ็ญ
่ฏพๅไฝไธ
้ฎ้ขๆ่ฟฐ
ๅๆ้พๆฅ๏ผ92. ๅ่ฝฌ้พ่กจ II
็ปไฝ ๅ้พ่กจ็ๅคดๆ้ head ๅไธคไธชๆดๆฐ left ๅ right ๏ผๅ
ถไธญ left <= right ใ่ฏทไฝ ๅ่ฝฌไปไฝ็ฝฎ left ๅฐไฝ็ฝฎ right ็้พ่กจ่็น๏ผ่ฟๅๅ่ฝฌๅ็้พ่กจ ใ
็คบไพ 1๏ผ
่พๅ
ฅ๏ผhead = [1,2,3,4,5], left = 2, right = 4
่พๅบ๏ผ[1,4,3,2,5]
็คบไพ 2๏ผ
่พๅ
ฅ๏ผhead = [5], left = 1, right = 1
่พๅบ๏ผ[5]
ๆ็คบ๏ผ
- ้พ่กจไธญ่็นๆฐ็ฎไธบ
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
ไปฃ็ ๅฎ็ฐ
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 {
ListNode last = null;
public ListNode reverseBetween(ListNode head, int left, int right) {
//left = 1
if(left == 1){
return reverseThN(head, right);
}
//1~left - 1
head.next = reverseBetween(head.next, left - 1, right - 1);
return head;
}
// ๅ่ฝฌ็ฌฌ1๏ฝn็่็น
ListNode reverseThN(ListNode head, int n){
if(n == 1){
last = head.next;
return head;
}
ListNode newHead = reverseThN(head.next, n - 1);
head.next.next = head;
head.next = last;
return newHead;
}
}
Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
last = None
def reverseBetween(self, head, left, right):
"""
:type head: ListNode
:type left: int
:type right: int
:rtype: ListNode
"""
if left == 1:
return self.reverseThN(head, right)
head.next = self.reverseBetween(head.next, left - 1, right - 1)
return head
def reverseThN(self, head, n):
if n == 1:
self.last = head.next
return head
newHead = self.reverseThN(head.next, n - 1)
head.next.next = head
head.next = self.last
return newHead
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 {
private:
ListNode* last = nullptr;
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (left == 1) {
return reverseThN(head, right);
}
head->next = reverseBetween(head->next, left - 1, right - 1);
return head;
}
ListNode* reverseThN(ListNode* head, int n) {
if (n == 1) {
last = head->next;
return head;
}
ListNode* newHead = reverseThN(head->next, n - 1);
head->next->next = head;
head->next = last;
return newHead;
}
};
Go