0%

重排链表

发表于 更新于 分类于 ， Disqus：

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

1
给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

1
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ListNode* reorderList(ListNode* head) {
		if (!head) return head;
		ListNode* h = head;
		vector<ListNode *> collection;
		while (h) {
			collection.push_back(h);
			h = h->next;
		}
		int size = collection.size();
		int n = size / 2;
		for (int i = 0; i < n; i++) {
			int right = size - 1 - i;
			collection[i]->next = collection[right];
			collection[right]->next = collection[i + 1];

			if (i == n - 1 && size % 2 == 0) {
				collection[right]->next = nullptr;
			}
			if (i == n - 1 && size % 2 != 0) {
				collection[right]->next->next = nullptr;
			}
		}
		return head;
	}