Leetcode - 143. Reorder List

문제

[1] [2] [3] ... [n-2] [n-1] [n] 순서의 링크드 리스트가 주어진다.
[1] [n] [2] [n-1] [3] [n-2] ... 순서로 재 정렬하라.

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

해결 stack - O(n) / O(n)

stack에 넣고 pop하면 뒤에서부터 거꾸로 노드를 얻을 수 있다. 원래 리스트와 스택에서 pop한 노드를 순차적으로 합치는 방법.

class Solution {
public:
    void reorderList(ListNode* head) {
        stack<ListNode *> st;
        ListNode *node = head;
        int node_cnt = 0;
        
        for (;node != NULL; node = node->next) {
            st.push(node);
            node_cnt++;
        }
        
        node = head;
        // 1 4 (2) 3 N
        for (int i = node_cnt/2; i > 0; i--) {
            ListNode *temp = st.top();
            st.pop();
            temp->next = node->next;
            node->next = temp;
            node = node->next->next;
        }
        node->next = NULL; // 이부분이 잘 이해가 안감.
    }
};