当前位置: 代码迷 >> 综合 >> leetcode 143. Reorder List (medium)
  详细解决方案

leetcode 143. Reorder List (medium)

热度:61   发布时间:2024-01-05 00:27:53.0
  1. 每一次翻转当前节点之后的所有节点,很花时间…
    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;}
};
  1. 优化时间
    可以找到中间节点,断开,把后半截单链表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; // cut at middlecout<<prev->val<<" ";slow = reverse(slow);cout<<slow->val<<" ";// merge two listsListNode *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;}
};
  相关解决方案