Leetcode - 92. Reverse Linked List II

문제

오름차순 정렬된 링크드리스트와 노드의 위치 인덱스 left, right가 주어질때, left에서 right까지의 범위를 reverse해라.

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

해결

아래의 쟁점을 해결 및 구현해야한다.

• 범위내의 리스트를 reverse 하기
• 그뒤 범위 밖의 prev_left, 와 next_head를 연결하기
• 주어진 left위치가 링크드리스트의 head위치일때 처리하기.

struct ListNode* reverse_list(struct ListNode* head, struct ListNode *next_right)
{
    struct ListNode *node = head, *prev = next_right, *tmp = head;
    for (; node != next_right; prev = node, node = tmp) {
        tmp = node->next;
        node->next = prev;
    }
    return prev;
}

기존의 reverse연산과 동일하고, 다만 prev 노드가 NULL이 아닌 next_right 로 초기화 한다는점이 다르다. 범위의 시작노드는 node->next 가 next_right를 가리켜야 하기 때문. 기존 reverse연산 참고: [C] Single Linked List 구현

struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
    struct ListNode *prev_left = head;
    struct ListNode *next_right = head;
    struct ListNode *new_head = malloc(sizeof(struct ListNode));
    new_head->next = head;
    struct ListNode *prev = new_head, *node = new_head;
    int node_cnt = 0;
    
    for (;node != NULL; prev = node, node = node->next) {
        if (node_cnt == left)
            prev_left = prev;
        if (node_cnt == right)
            next_right = node->next;
        node_cnt++;
    }
    prev_left->next = reverse_list(prev_left->next, next_right);
    return new_head->next;
}

그 뒤에 prev_left->next에 reverse된 리스트를 할당한다.