[LeetCode] 707. Design Linked List, Medium

2025. 3. 13. 17:20·CodingTest/LeetCode
반응형

1. 문제

  • 단일 연결 리스트 혹은 이중 연결 리스트를 만들어라. 조건은 다음과 같다.
    • 생성자로 객체를 생성하며, 매개변수는 받지 않는다.
    • get 함수는 index를 매개변수로 받고 해당 인덱스의 value롤 반환하고, 없으면 -1을 반환하라.
    • addAtHead 함수는 새로운 노드를 연결 리스트의 맨 처음에 추가하라.
    • addAtTail 함수는 새로운 노드를 연결 리스트의 맨 마지막에 추가하라.
    • addAtIndex 함수는 주어진 인덱스에 새로운 노드를 추가하되, 만약 인덱스가 전체 길이와 같을 때도 추가하고 전체 길이보다 큰 경우는 무시한다.
    • deleteAtIndex 함수는 해당 index의 노드를 제거하라.

2. 해결

class Node { // 노드 클래스
    value: number;
    next: Node | null;
    constructor(value: number) {
        this.value = value;
        this.next = null;
    }
}

class MyLinkedList { // 단일 연결 리스트.
    head: Node | null;
    size: number;

    constructor() { // 생성자.
        this.head = null;
        this.size = 0;
    }

    get(index: number): number { // get 함수.
        let pointer = this.head; 
        let idx = 0;

        while (pointer) { // pointer가 null이 아닐 때 까지 반복.
            if (idx === index) return pointer.value; // index가 일치하는 Node의 value 반환.
            pointer = pointer.next; // 다음 노드로 갱신.
            idx++; // 현재 인덱스 갱신.
        }

        return -1; // 없으면 -1 반환.
    }

    addAtHead(val: number): void { // addAtHead 함수.
        const newNode = new Node(val); // 새로운 노드.
        newNode.next = this.head; // 현재 head를 새로운 노드의 next로 지정.
        this.head = newNode; // 새로운 노드를 head로 지정.
        this.size++; // size 증가.
    }

    addAtTail(val: number): void { // addAtTail 함수.
        const newNode = new Node(val); // 새로운 노드.

        if (!this.head) { // 비어 있으면, head로 지정.
            this.head = newNode;
        } else { // 비어 있지 않으면,
            let pointer = this.head;
            while (pointer.next) { // node를 탐색해서 next가 null인 노드를 찾고.
                pointer = pointer.next;
            }
            pointer.next = newNode; // 해당 노드의 next에 새로운 노드를 지정.
        }

        this.size++; // size 증가.
    }

    addAtIndex(index: number, val: number): void { // addAtIndex 함수.
        if (index > this.size) return; // index가 size보다 크면 무시.

        if (index === 0) { // index가 0이면 addAtHead 함수 호출.
            this.addAtHead(val);
            return;
        }

        const newNode = new Node(val); // 새로운 노드 생성.
        let pointer = this.head;
        let idx = 0;

        while (pointer && idx < index - 1) { // 변경 위치 노드 탐색.
            pointer = pointer.next;
            idx++;
        }

        if (pointer) { // 만약 변경 위치에 노드가 존재하면, 
            newNode.next = pointer.next; // 해당 노드의 next를 새로운 노드의 next로 지정.
            pointer.next = newNode; // 해당 노드의 next를 새로운 노드로 지정.
            this.size++; // size 증가.
        }
    }

    deleteAtIndex(index: number): void { // deleteAtIndex 함수.
        if (index < 0 || index >= this.size) return; // 범위를 벗어나는 index는 무시.

        if (index === 0) { // 0번 인덱스를 지우는 경우,
            this.head = this.head!.next; // 현재 head의 next를 head로 지정.
        } else { // 그 외.
            let pointer = this.head;
            let idx = 0;

            while (pointer && idx < index - 1) { // 삭제 위치 노드 탐색.
                pointer = pointer.next;
                idx++;
            }

            if (pointer && pointer.next) { // 삭제 위치 노드의 next 갱신.
                pointer.next = pointer.next.next;
            }
        }

        this.size--; // size 감소.
    }
}
  • 일반적인 연결 리스트 구현이 아니라 몇몇 조건들이 있어서 애좀 먹었다. 침착하게 풀면 괜찮을 거 같다.

 

저작자표시 (새창열림)
'CodingTest/LeetCode' 카테고리의 다른 글
  • [LeetCode] 142. Linked List Cycle II, Medium
  • [LeetCode] 141. Linked List Cycle, Easy
  • [LeetCode] 557. Reverse Words in a String III, Easy
  • [LeetCode] 151. Reverse Words in a String, Medium
뜸부깅
뜸부깅
코딩에 대한 여러 개인적인 생각을 정리하고 공부를 하는 공간입니다!!
  • 뜸부깅
    코오오딩
    뜸부깅
  • 전체
    오늘
    어제
    • Note (429)
      • Skill (31)
        • Java & Spring (9)
        • Javascript & HTML & CSS (0)
        • React (0)
        • Next.js (22)
      • CodingTest (389)
        • 백준 온라인 저지(BOJ) (140)
        • 프로그래머스(Programmers) (79)
        • LeetCode (170)
      • Algorithm & Data Structure (6)
      • [Project] 포트폴리오 (3)
        • Front end (3)
        • Back end (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    component-scan
    백준1427
    medium
    백준2751
    boj2108
    프로그래머스
    TypeScript
    leetcode 2236
    백준
    Java
    백준1260
    백준7576
    next 14
    자바
    Easy
    알고리즘
    백준7576자바
    BOJ
    meidum
    boj1427
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
뜸부깅
[LeetCode] 707. Design Linked List, Medium
상단으로

티스토리툴바