320x100
https://leetcode.com/problems/reverse-linked-list-ii/
단방향의 링크드리스트와 left, right 값이 주어졌을 때, left와 right 사이에 해당하는 Node들을 reverse 하는 문제다.
너무 오랜만에 풀어서 그런가 링크드리스트 뒤집는것도 생각이 안나고 범위가 주어지니 또 헤매고..
아는 건데도 어렵고 개념이 조금만 바뀌면 어렵다..
/**
* 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* reverse(ListNode* head, ListNode* tail, int count) {
ListNode* p, *q, *r;
p = head;
q = tail;
while (count) {
r = q;
q = p;
p = p->next;
q->next = r;
--count;
}
return q;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head)
return nullptr;
if (left == right)
return head;
ListNode* ret = head;
ListNode* left_prev = head;
ListNode* left_ptr = nullptr;
ListNode* right_next = nullptr;
int count = 0;
while (head)
{
++count;
if (count < left)
left_prev = head;
else if (count == left)
left_ptr = head;
if (count == right + 1)
{
right_next = head;
break;
}
head = head->next;
}
left_ptr = reverse(left_ptr, right_next, right - left + 1);
if (left == 1)
return left_ptr;
left_prev->next = left_ptr;
return ret;
}
};
320x100
'코딩테스트 준비 > leetcode' 카테고리의 다른 글
40. Combination Sum II (0) | 2021.11.09 |
---|---|
39. Combination Sum (0) | 2021.11.07 |
21. Merge Two Sorted Lists (0) | 2021.09.22 |
20. Valid Parentheses (0) | 2021.09.21 |
90. Subsets II (0) | 2021.09.01 |