Back-To-CP: 2일차

2022년 10월 14일

Delete the Middle Node of a Linked List

문제는 매우 간단합니다. 단일 연결 목록의 주어진 헤드로 중간 노드를 삭제합니다. 의 정의는 middle = n/2로 지정됩니다. 여기서 n은 목록의 길이입니다.
단일 연결 리스트이기 때문에 검정으로의 순회는 불가능합니다. 따라서 중간 노드 또는 중간 - 1의 이전 노드로 이동해야 합니다.
헤드만 주어지기 때문에 길이를 계산하기 위해 순회가 필요합니다. 그런 다음 연결을 끊습니다.

/**
 * 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* deleteMiddle(ListNode* head) {
        if(head->next == nullptr){
            return nullptr;
        }
        int count = 0;
        ListNode* ptr = head;
        ListNode* ptr2 = head;

        while(ptr != nullptr){
            count++;
            ptr = ptr->next;
        }
        for(int i = 0; i < (count / 2) - 1; i++){
            ptr2 = ptr2->next;
        }

        ptr2->next = ptr2->next->next;
        return head;
    }
};

수락한 후 나는 이 문제를 해결할 다른 효율적인 방법을 찾았고 느린 포인터 빠른 포인터라는 새로운 방법을 배웠습니다.
이것은 크기를 알 수 없는 목록의 중간을 찾는 매우 간단한 기술입니다. 처음부터 시작하는 느린 포인터와 빠른 포인터가 있습니다. 빠른 노드는 느린 노드보다 두 배 더 증가합니다. 결과적으로 빠른 노드가 이미 끝에 도달하면 느린 포인터가 중간에 있게 됩니다.

첫 번째 시도에서 오류가 발생했습니다.runtime error: member access within null pointer of type 'ListNode' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior~을 위한while(f != nullptr || f->next != nullptr){
f = f->next->next;
s = s->next;
}포인터가 null이 아닌지 두 가지를 모두 확인해야 하는지 밝혀졌습니다.

두 번째 시도에서 동일한 오류가 발생했습니다. 이전에 빠른 포인터를 초기화했기 때문에 길이가 1인 목록인 경우 존재하지 않는 fast->next->next에 액세스하는 오류가 발생합니다.
그래서 엣지 케이스가 필요했습니다.

/**
 * 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* deleteMiddle(ListNode* head) {

        if(head->next == nullptr){
            return 0;
        }

        ListNode *s = head;
        ListNode *f = head->next->next;

        while(f != nullptr && f->next != nullptr){
            f = f->next->next;
            s = s->next;
        }

        s->next = s->next->next;
        return head;
        return head;
    }
};

Reverse String

내 접근 방식은 간단했습니다. 시작과 끝에 두 개의 포인터가 있습니다. 두 포인터를 교환하고 그에 따라 포인터를 증가 및 감소시킵니다.

class Solution {
public:
    void reverseString(vector<char>& s) {
        int l = 0, h = s.size() - 1;
        while(l < h){
            swap(s[l], s[h]);
            l++;
            h--;
        }
    }
};