[LeetCode] 430. Flatten a Multilevel Doubly Linked List, Medium

2025. 4. 1. 13:57·CodingTest/LeetCode
반응형

  • child라는 필드를 추가적으로 가지는 멀티 레벨 이중 연결 리스트가 주어질 때, 모든 child를 없애 단일 이중 연결 리스트로 재구성 하라.

2. 해결

/**
 * Definition for _Node.
 * class _Node {
 *     val: number
 *     prev: _Node | null
 *     next: _Node | null
 *     child: _Node | null
 *     
 *     constructor(val?: number, prev? : _Node, next? : _Node, child? : _Node) {
 *         this.val = (val===undefined ? 0 : val);
 *         this.prev = (prev===undefined ? null : prev);
 *         this.next = (next===undefined ? null : next);
 *         this.child = (child===undefined ? null : child);
 *     }
 * }
 */

function recursive(head: _Node, curr: _Node | null) {
    let p1 = head;
    
    while(p1) {
        if(p1.child) { // 자식이 있으면 재귀.
            const lastChildNode = recursive(p1.child, p1); // 아래를 통해 자식 리스트의 마지막 노드 반환.
            p1.next = p1.child  // 현재 자식 노드를 다음 노드로 연결.
            p1.next.prev = p1; // 자식 노드였던 노드의 prev를 연결.
            p1.child = null; // 자식은 null로 변경.
            p1 = lastChildNode; // 위에서 받은 마지막 노드로 포인터로 연결.
            continue;
        } else if(!p1.next && curr) { // 최하위 레벨의 마지막 노드인 경우,
            p1.next = curr.next; // 부모 노드의 다음 노드와 연결.
            if(curr.next) // 부모 노드의 다음 노드가 있으면,
            curr.next.prev = p1; // 해당 노드의 prev도 연결.
            return p1;
        }        
        p1 = p1.next;
    }
}

function flatten(head: _Node | null): _Node | null {
    recursive(head, null);
    
    
    return head;
};
  • 비슷한 형태로 연산이 반복된다면 재귀를 활용하자. 
  • 자식 노드의 첫 번째, 마지막 노드와 자식 노드가 있는 노드에 대한 연산이 키 포인트이다.
저작자표시 (새창열림)
'CodingTest/LeetCode' 카테고리의 다른 글
  • [LeetCode] 61. Rotate List, Medium
  • [LeetCode] 138. Copy List with Random Pointer, Medium
  • [LeetCode] 2. Add Two Numbers, Medium
  • [LeetCode] 21. Merge Two Sorted Lists, Easy
뜸부깅
뜸부깅
코딩에 대한 여러 개인적인 생각을 정리하고 공부를 하는 공간입니다!!
  • 뜸부깅
    코오오딩
    뜸부깅
  • 전체
    오늘
    어제
    • 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)
  • 블로그 메뉴

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

  • 공지사항

  • 인기 글

  • 태그

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

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
뜸부깅
[LeetCode] 430. Flatten a Multilevel Doubly Linked List, Medium
상단으로

티스토리툴바