[連結清單]BM12 單連結清單的排序-中等

​​BM12 單連結清單的排序​​

描述

給定一個節點數為n的無序單連結清單，對其按升序排序。

資料範圍：

要求：時間複雜度 

示例1

輸入：

{1,3,2,4,5}      

複制傳回值：

{1,2,3,4,5}      

複制

示例2

輸入：

{-1,0,-2}      

{-2,-1,0}      

題解

• 找到連結清單的尾節點
• 以頭尾節點為參數進行歸并排序
• 歸并排序：

• 找到頭尾節點的中間節點，以中間節點為界将連結清單劃分成2部分，一定要将中間節點的next指針設定為空
• 對劃分後的2個連結清單分别使用歸并排序，得到2個有序的連結清單
• 将2個有序連結清單連接配接起來，得到新的有序連結清單
• 排序完成

#include <bits/stdc++.h>

struct ListNode
{
  int val;
  struct ListNode *next;
  ListNode(int x) : val(x), next(nullptr)
  {
  }
  ListNode() = default;
};

void swap_node(ListNode *left, ListNode *right)
{
  std::swap(left->val, right->val);
}

ListNode *find_mid_node(ListNode *left, ListNode *right)
{
  ListNode *slow = left;
  ListNode *fast = left;
  while (fast != right && fast->next != right)
  {
    slow = slow->next;
    fast = fast->next->next;
  }

  return slow;
}

ListNode *link_sorted_list(ListNode *left, ListNode *right)
{
  if (left == nullptr)
  {
    return right;
  }
  if (right == nullptr)
  {
    return left;
  }
  if (left->val > right->val)
  {
    return link_sorted_list(right, left);
  }
  auto head = left;
  auto tail_node = head;
  left = left->next;
  // 這裡其實是可以優化的，當某一個連結清單的指針為空的時候，跳出循環，然後直接讓tail_node->next指向非空連結清單即可！！
  while (left != nullptr || right != nullptr)
  {
    if (left == nullptr)
    {
      auto next = right->next;
      tail_node->next = right;
      tail_node = tail_node->next;
      right = next;
      continue;
    }
    if (right == nullptr)
    {
      auto next = left->next;
      tail_node->next = left;
      tail_node = tail_node->next;
      left = next;
      continue;
    }
    if (left->val <= right->val)
    {
      tail_node->next = left;
      left = left->next;
      tail_node = tail_node->next;
    }
    else
    {
      tail_node->next = right;
      right = right->next;
      tail_node = tail_node->next;
    }
  }
  return head;
}

ListNode *merge_sort(ListNode *left, ListNode *right)
{
  if (left == nullptr)
  {
    return right;
  }
  if (right == nullptr)
  {
    return left;
  }
  if (left == right)
  {
    return left;
  }

  auto mid_node = find_mid_node(left, right);
  auto next_node = mid_node->next;
  mid_node->next = nullptr;
  auto pre_list = merge_sort(left, mid_node);
  auto after_list = merge_sort(next_node, right);
  return link_sorted_list(pre_list, after_list);
}

ListNode *sortInList(ListNode *head)
{
  if (head == nullptr || head->next == nullptr)
  {
    return head;
  }

  auto cur_node = head;
  while (cur_node->next != nullptr)
  {
    cur_node = cur_node->next;
  }
  return merge_sort(head, cur_node);
}

ListNode *create_list(const std::vector<int> &v)
{
  ListNode head;
  ListNode *phead = &head;
  for (auto &data : v)
  {
    auto node = new ListNode;
    node->val = data;
    node->next = nullptr;
    phead->next = node;
    phead = phead->next;
  }
  return head.next;
}

int main()
{
  // auto list = create_list(std::vector<int>{105, 25, 89, 67, 49, 38, 52});
  auto list = create_list(std::vector<int>{1, 3, 2, 4, 5});
  auto head = sortInList(list);
  while (head != nullptr)
  {
    std::cout << head->val << " ";
    head = head->next;
  }
  std::cout << std::endl;
  return 0;
}