[LeetCode] 143. Reorder List

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

Leetcode - Reorder List

문제 유형 : 연결리스트, 스택

문제 난이도 : Medium

 

문제

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.

 

연결리스트의 head가 주어진다.

연결리스트를 위와 같이 재정렬하시오.

값을 바꿔서는 안됩니다.

 

풀이

우선, 한 번 연결리스트를 순회하여 크기를 알아낸다.

그 다음, 다시 처음부터 절반만큼 이동한다. 홀수일 경우, 한칸 더 이동한다.

 

이제 뒷 부분의 포인터들을 순차적으로 스택에 담는다.

다시 처음으로 이동하여, 기존 절반 앞의 노드들의 사이에 끼워넣는다.

그 뒤, 기존 뒷부분의 연결을 제거해주면 된다.

 

코드

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    void reorderList(ListNode* head) {
        stack<ListNode*> s;
        int n = 0;

        auto node = head;
        while(node != NULL) {
            n++;
            node = node -> next;
        }

        if(n < 3) return;

        node = head;
        for(int i = 0; i < n/2 + (n%2); i++) {
            node = node -> next;
        }

        while(node != NULL) {
            s.push(node);
            node = node -> next;
        }

        node = head -> next;
        auto prev = head;

        while(!s.empty()) {
            prev -> next = s.top();
            s.top() -> next = node;
            s.pop();
            prev = node;
            node = node -> next;
        }

        if(n%2) {
            node = node -> next;
        }

        node -> next = NULL;
    }
};