leet code 문제풀이

linked list 완료

1225 - Flatten a Multilevel Doubly Linked List

C++ time(beats 79.87%), space(beats 54.09%)

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution {
public:
    Node* flatten(Node* head) {
        if(!head) return head;
        Node* last = head;
        Node* cur = head;
        Node* branchPtrArr[1010];
        int top = 0;

        branchPtrArr[0] = head;
        top++;

        // 그리고 child에서 탐색
        // child에서 nullptr까지 도달하면, 종료
        while (top)
        {
            while (cur)
            {
                // 만약 child가 있는 노드를 만나면
                // branchPtrArr에 cur->next 노드 추가
                if (cur->child)
                {
                    if (cur->next)
                    {
                        branchPtrArr[top] = cur->next;
                        top++;
                    }
                    cur->next = cur->child;
                    cur->next->prev = cur;
                    cur->child = nullptr;
                }

                if (!(cur->next))
                {
                    if (top == 1) top--;
                    if (top>1)
                    {
                        last = branchPtrArr[top - 1];
                        cur->next = last;
                        last->prev = cur;
                        top--;
                    }
                }
                // 오른쪽으로 가기
                cur = cur->next;
            }
        }

        return head;
    }
};

나는 코드를 좀 더 길게 썼는데, DFS에 의한 inorder 탐색으로 짧게 풀이가 가능하다고 합니다.

Node tail = null;
public Node flatten(Node head) {
    if(head == null) return null;

    head.prev = tail;
    tail = head;

    Node nextNode = head.next;

    head.next = flatten(head.child);
    head.child = null;

    tail.next = flatten(nextNode);

    return head;
}

1229 - Copy List with Random Pointer

C++ time(beats 73.83%), space(beats 37.11%)

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* orgLst[10001] = { nullptr, };
        Node* dstLst[10001] = { nullptr, };
        int orgTop = 0;
        int dstTop = 0;

        Node* ptr = head;
        while (ptr)
        {
            orgLst[orgTop] = ptr;
            orgTop++;
            ptr = ptr->next;
        }

        Node* rsltHead = new Node(0);
        ptr = head;
        Node* dstPtr = rsltHead;
        for (int i = 0; i < orgTop; ++i)
        {
            Node* newNode = new Node(ptr->val);
            dstPtr->next = newNode;

            ptr = ptr->next;
            dstPtr = dstPtr->next;
            dstLst[dstTop] = newNode;
            dstTop++;
        }

        ptr = head;
        dstPtr = rsltHead->next;
        int idx = 0;
        for (int i = 0; i < orgTop; ++i)
        {
            if (ptr->random)
            {
                idx = getIndex(orgLst, ptr->random);
                dstPtr->random = dstLst[idx];
            }

            ptr = ptr->next;
            dstPtr = dstPtr->next;
        }
        return rsltHead->next;
    }

private:
    int getIndex(Node* lst[], Node* address)
    {
        int i = 0;
        for (; i < 10001; ++i)
        {
            if (address == lst[i]) break;
        }
        return i;
    }
};