leetcode 143) Reorder List

LV. Medium 🧐

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

Reorder List - LeetCode

 

문제

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

 

문제 해결법

앞과 뒤의 값을 순차적으로 가져와 새로운 리스트를 만들기

새로운 리스트가 가지고 있을 val값을 저장할 백터를 만들어 저장 후 마지막에 다시 nodelist에 val 값을 넣어줬다

 

아래 nodelist가 있다고 생각하자

[1, 2, 3, 4]

제일 앞의 값 1을 첫 번째의 새로운 리스트의 val값으로 가져온다

앞의 값을 사용했을때는 -1으로 바꿔준다

[-1, 2, 3, 4] -> [1]

이제 제일 뒤의 값 4을 0으로 바꿔준다

그리고 뒤의 값은 사용했으면 0으로 바꿔준다

[-1, 2, 3, 0] -> [1, 4]

이제 앞에서부터 -1가 없을 때까지 뒤로 간 다음에 나온 수 2를 가져온다

그리고 2를 사용했으니 앞의 값이니깐 -1로 바꿔준다

[-1, -1, 3, 0] -> [1, 4, 2]

뒤의 값을 가져올 차례니깐 앞에서부터 0이 있을때까지 뒤로 간 다음 앞의 값인 3을 가져온다

3을 사용했으니 0으로 바꿔주면 새로운 리스트 [1, 4, 2, 3]가 만들어졌다

 

해결 코드

class Solution {
public:
	void reorderList(ListNode* head) {
		vector<int> reorder;

		while (1) {
			// first node
			reorder.push_back(first_node(head));
			if (reorder.back() <= 0)
				break ;

			//last node
			reorder.push_back(last_node(head));
			if (reorder.back() <= 0)
				break ;
		}
		// 완성된 값을 head에 저장
		int i = 0;
		while (head) {
			head->val = reorder[i];
			head = head->next;
			i++;
		}
	}
	int first_node(ListNode* head) {
		ListNode *start = head;
		int val;

		while (start && start->val == -1) {
			start = start->next;
		}
		if (!start)
			return 0;
		val = start->val;
		start->val = -1;
		return val;
	}
	int last_node(ListNode* head) {
		ListNode *last = head;
		ListNode *before = head;
		int val;

		while (last && last->val != 0 && last->next) {
			val = last->val;
			before = last;
			last = last->next;
		}
		if (last->val == 0) {
			before->val = 0;
			return val;
		}
		if (!last->next) {
			val = last->val;
			last->val = 0;
			return val;
		}
		return 0;
	}
};