코딩테스트 준비/leetcode

92. Reverse Linked List II

MAKGA 2021. 11. 10. 00:00
320x100

https://leetcode.com/problems/reverse-linked-list-ii/

 

Reverse Linked List II - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

단방향의 링크드리스트와 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