연결 리스트 요소 제거

문제 설명:

주어진 연결 리스트에서 특정 값을 가진 모든 노드를 제거하는 문제이다.

解题 전략:

노드를 삭제할 때 현재 노드의 next 포인터를 다음 노드의 next로 변경하면 된다. 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 {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 더미 노드를 생성하여 연결 리스트의 헤드 처리 복잡도 감소
        ListNode* sentinel = new ListNode(0);
        sentinel->next = head;
        
        ListNode* current = sentinel;
        while(current->next != nullptr) {
            // 목표 값과 일치하는 노드를 발견하면 해당 노드 삭제
            if(current->next->val == val) {
                ListNode* target = current->next;
                current->next = current->next->next;
                delete target;
            } else {
                // 값이 일치하지 않으면 다음 노드로 이동
                current = current->next;
            }
        }
        
        head = sentinel->next;
        delete sentinel;
        return head;
    }
};

핵심 포인트:

• 더미 노드를 활용하면 헤드 노드 삭제 케이스를 일반화할 수 있다
• 삭제된 노드의 메모리를 반드시 해제해야 한다

연결 리스트 구현

문제 설명:

연결 리스트를 직접 구현하는 문제로, 다음 연산들을 지원해야 한다: 특정 인덱스 값 조회, 헤드에 노드 추가, 테일에 노드 추가, 특정 위치에 노드 삽입, 특정 위치 노드 삭제.

解题 전략:

연결 리스트의 크기를 멤버 변수로 저장하면 경계 조건 체크를 단순화할 수 있다. 모든 연산에서 크기 정보를 활용하여 효율적인 구현이 가능하다.

구현 코드:

class MyLinkedList {
private:
    struct Node {
        int value;
        Node* next;
        Node(int val) : value(val), next(nullptr) {}
    };
    
    Node* dummyHead;
    int elementCount;
    
public:
    MyLinkedList() {
        dummyHead = new Node(0);
        elementCount = 0;
    }
    
    // 인덱스에 해당하는 값 조회
    int get(int index) {
        if(index < 0 || index >= elementCount) {
            return -1;
        }
        
        Node* cursor = dummyHead->next;
        for(int i = 0; i < index; i++) {
            cursor = cursor->next;
        }
        return cursor->value;
    }
    
    // 헤드에 노드 추가
    void addAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        elementCount++;
    }
    
    // 테일에 노드 추가
    void addAtTail(int val) {
        Node* cursor = dummyHead;
        while(cursor->next != nullptr) {
            cursor = cursor->next;
        }
        Node* newNode = new Node(val);
        cursor->next = newNode;
        elementCount++;
    }
    
    // 특정 인덱스에 노드 삽입
    void addAtIndex(int index, int val) {
        if(index > elementCount) {
            return;
        }
        if(index < 0) {
            index = 0;
        }
        
        Node* cursor = dummyHead;
        for(int i = 0; i < index; i++) {
            cursor = cursor->next;
        }
        
        Node* newNode = new Node(val);
        Node* temp = cursor->next;
        cursor->next = newNode;
        newNode->next = temp;
        elementCount++;
    }
    
    // 특정 인덱스의 노드 삭제
    void deleteAtIndex(int index) {
        if(index < 0 || index >= elementCount) {
            return;
        }
        
        Node* cursor = dummyHead;
        for(int i = 0; i < index; i++) {
            cursor = cursor->next;
        }
        
        Node* target = cursor->next;
        cursor->next = cursor->next->next;
        delete target;
        elementCount--;
    }
};

핵심 포인트:

• delete 연산 후 포인터를 nullptr로 설정하여 와일드 포인터 방지
• 크기 정보를 관리하면 경계 조건 처리가 용이

연결 리스트 뒤집기

문제 설명:

주어진 연결 리스트의 노드 순서를 반대로 뒤집는 문제이다.

解题 전략:

뒤집기 과정에서 핵심은 현재 노드의 다음 노드를 미리 저장하는 것이다. 순차적으로 진행하면서 각 노드의 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* reverseList(ListNode* head) {
        ListNode* previous = nullptr;
        ListNode* current = head;
        ListNode* nextNode;
        
        while(current != nullptr) {
            // 현재 노드의 다음 노드를 미리 저장
            nextNode = current->next;
            
            // 현재 노드의 next를 이전 노드로 변경
            current->next = previous;
            
            // 이전 노드와 현재 노드를 한 칸씩 이동
            previous = current;
            current = nextNode;
        }
        
        return previous;
    }
};

핵심 포인트:

• nextNode 변수로 다음 위치를 저장하지 않으면链表 구조가 끊어짐
• 반복 종료 후 previous가新的 헤드가 됨