leetcode 143. 重排链表
题目详情
题目链接 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1: 给定链表 1->2->3->4, 重新排列为 1->4->2->3.示例 2: 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
我的代码
class Solution {
public:
void reorderList(ListNode
* head
) {
if (!head
|| !head
->next
|| !head
->next
->next
) {
return;
}
vector
<ListNode
*> nodes
;
while (head
) {
nodes
.push_back(head
);
head
= head
->next
;
}
int left
= 0, right
= nodes
.size() - 1;
while (left
< right
) {
nodes
[left
]->next
= nodes
[right
];
nodes
[right
]->next
= nodes
[left
+ 1];
++left
, --right
;
}
if (nodes
.size() % 2) {
nodes
[right
]->next
= nullptr;
} else {
nodes
[left
]->next
= nullptr;
}
}
};
我的成绩
执行结果：通过 执行用时：68 ms, 在所有 C++ 提交中击败了31.46%的用户 内存消耗：18.9 MB, 在所有 C++ 提交中击败了5.05%的用户
一些想法
本道题我使用了数组来存储链表的内容。
执行用时为 32 ms 的范例
class Solution {
public:
void reorderList(ListNode
* head
) {
int n
= 0;
for (ListNode
*p
= head
; p
; p
= p
->next
) n
++ ;
if (n
<= 2) return;
ListNode
*later
= head
;
for (int i
= 0; i
+ 1 < (n
+ 1) / 2; i
++ )
later
= later
->next
;
ListNode
*a
= later
, *b
= later
->next
;
while (b
)
{
ListNode
*c
= b
->next
;
b
->next
= a
;
a
= b
;
b
= c
;
}
later
->next
= 0;
while (head
&& head
!= a
)
{
b
= a
->next
;
a
->next
= head
->next
;
head
->next
= a
;
head
= head
->next
->next
;
a
= b
;
}
}
};
思考
参见官方解答
