- 每一次翻转当前节点之后的所有节点,很花时间…
Runtime: 1760 ms, faster than 5.08% of C++ online submissions for Reorder List.
class Solution
{
public:void reorderList(ListNode *head){
if (head == nullptr || head->next == nullptr)return;for(ListNode *cur = head; cur != nullptr;){
cur->next = reverse(cur->next);cur = cur->next;}}ListNode *reverse(ListNode *begin){
if (begin == nullptr || begin->next == nullptr)return begin;ListNode *pre = begin;for (ListNode *cur = pre->next, *next = cur->next; cur != nullptr;){
cur->next = pre;pre = cur;cur = next;next = next ? next->next : nullptr;}begin->next = nullptr;return pre;}
};
- 优化时间
可以找到中间节点,断开,把后半截单链表reverse一下,再合并两个单链表
Runtime: 48 ms, faster than 99.57% of C++ online submissions for Reorder List.
参考这篇博文
class Solution
{
public:void reorderList(ListNode *head){
if (head == nullptr || head->next == nullptr)return;ListNode *slow = head, *fast = head, *prev = nullptr;while (fast && fast->next){
prev = slow;slow = slow->next;fast = fast->next->next;}prev->next = nullptr; cout<<prev->val<<" ";slow = reverse(slow);cout<<slow->val<<" ";ListNode *curr = head;while (curr->next){
ListNode *tmp = curr->next;curr->next = slow;slow = slow->next;curr->next->next = tmp;curr = tmp;}curr->next = slow;}ListNode *reverse(ListNode *begin){
if (begin == nullptr || begin->next == nullptr)return begin;ListNode *pre = begin;for (ListNode *cur = pre->next, *next = cur->next; cur != nullptr;){
cur->next = pre;pre = cur;cur = next;next = next ? next->next : nullptr;}begin->next = nullptr;return pre;}
};