C++ ] leetCode 143 - Reorder List

 

 

리트코드 143번 문제

 

 

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.

 

 

Example 1:

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

 

 

Example 2:

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

 

 

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

 

 

주어진 리스트를 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 순서로 재배치하면 되는 문제다.

 

먼저 벡터에 모든 노드를 저장해두고, front(0)와 back(벡터 사이즈 - 1) 인덱스를 사용해 접근해서 next 포인터를 조작하여 리스트를 재배치한다. front, back 인덱스를 계속 증감하며 인덱스가 중간에서 만난 경우 루프를 탈출하고 마지막 노드의 next를 nullptr로 만든다.

 

 

 

 

/**
 * 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) {
        if(head->next == nullptr) return;
        vector<ListNode*> vNodes;
        ListNode* p = head;
        while(p != nullptr) {
            vNodes.push_back(p);
            p = p->next;
        }

        int front = 0;
        int back = vNodes.size() - 1;

        while(1) {        	
            vNodes[front]->next = vNodes[back];            
            front++;
            if(front == back) break;

            vNodes[back]->next = vNodes[front];
            back--;
            if(front == back) break;
        }
        vNodes[front]->next = nullptr;
    }
};