[ leetcode 문제풀이 ] Reorder List

https://leetcode.com/problems/reorder-list/

Reorder List - LeetCode

(Reorder List 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Reorder List 문제 설명 >

 

Reorder List 문제는 다음과 같다.

You are given the head of a singly linked-list. The list can be represented as: 
    L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
    L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.

 

singly linked-list가 주어질 때(L0 → L1 → … → Ln - 1 → Ln) 순서를 재정렬해 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 와 같은 형태가 되도록 하여라. list 노드의 값은 변화시킬 수 없고, 오직 노드 자체만 변경할 수 있다.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

주어진 제한조건은 다음과 같다:

list 노드의 수는 [1, 5*10^4] 범위 내에 있다.

1  ≤  Node.val  ≤ 1000

 

 

 

---

< Reorder List 문제 접근(1) >

 

먼저 related topics에 있는 stack data structure을 이용해 알고리즘을 구현해보자.

 

stack에 ListNode를 순서대로 쌓은 후 전체 노드 중 뒤에서 절반에 해당하는 노드를 기존 list 중간중간에 삽입하면 될 것이다. (ex:1 → 2 →  3 →  ... →  n 이 있다고 할 때 stack에 ListNode를 저장하면 stack의 top은 n임. 이를 list 중간에 삽입한다.

1 →  n → 2 →  3 →  ... / now stack.top == n-1)

 

작성한 코드는 다음과 같다. (Cpp 사용)

 

#include <stack>

void reorderList(ListNode* head) {
    if(!(head->next)) return;
        
    ListNode* pointNode = head->next;
    stack<ListNode*> NodeStack;
    while(pointNode){
        NodeStack.push(pointNode);
        pointNode = pointNode->next;
    }
        
    pointNode = head;

    while(pointNode != pointNode->next && pointNode != NodeStack.top()){
        ListNode* elem = NodeStack.top();
        NodeStack.pop();
        elem->next = pointNode->next;
        pointNode->next = elem;
        pointNode = elem->next;
    }
    pointNode->next = nullptr;
} // runtime : 54 ms (faster than 59.95 %), memory usage : 18.6 MB (less than 23.60 %)
// algorithm using stack

 

 

 

---

< Reorder List 문제 접근(2) >

 

stack을 사용해서 작성하고 나니 굳이 stack을 써야하나? 생각이 들었다. ListNode의 앞뒤에서 노드를 찾아서 연결하면 되는 것이므로 이번에는 deque(double-ended queue)를 사용해보았다. deque에 ListNode를 모두 저장해두고, connectNode라는 함수를 재귀적으로 호출해 deque set의 앞, 뒤에서 번갈아가며 ListNode를 연결하였다.

 

작성한 코드는 다음과 같다. (Cpp 사용)

 

#include <deque>

void connectNode(ListNode* pointNode, deque<ListNode*>& NodeSet, bool popFront){
    if(NodeSet.empty()){
        pointNode->next = nullptr;
        return;
    }
        
    ListNode* elem;
    if(popFront){
        elem = NodeSet.front();
        NodeSet.pop_front();
        pointNode->next = elem;
    }
    else{
        elem = NodeSet.back();
        NodeSet.pop_back();
        pointNode->next = elem;
    }
    connectNode(elem, NodeSet, !popFront
}
void reorderList(ListNode* head) {
    if(!(head->next)) return;
    
    ListNode* pointNode = head->next;
    deque<ListNode*> NodeSet;
    while(pointNode){
        NodeSet.push_back(pointNode);
        pointNode = pointNode->next;
    }
       
    pointNode = head;
    connectNode(pointNode, NodeSet, false);
} // runtime : 56 ms (faster than 56.42 %), memory usage : 18.6 MB (less than 23.60 %)
// algorithm using deque

 

stack과 deque를 사용해 두 가지 방법으로 알고리즘을 작성해보았는데, 본질적으로 n개의 노드가 있다고 할 때 n개의 연결관계를 수정해야 하기에 runtime / memory usage 측면에서 동일한 성능을 나타낸 것으로 보인다.