题解 | #重排链表#

将len/2后的节点单独拿出来为l2链表，len/2前的链表为l1链表。然后合并两个链表即可。细节真多啊。。。

class Solution {
public:
  void reorderList(ListNode* head) {
    if (!head) return;
    int len = 0;
    ListNode* tmp_head = head;
    ListNode* tail = nullptr;
    ListNode* tmp = nullptr;
    ListNode* l1 = nullptr, * l2 = nullptr;
    while (head)
    {
      head = head->next;
      len++;
    }
    if (len <= 2) return;
    head = tmp_head;
    int i = 1;
    while (i < len / 2)
    {
      head = head->next;
      i++;
    }
    if (len % 2 == 1)
    {
      head = head->next;
      tail = head;
      tmp = head->next;
      head->next = nullptr;

    }
    else
    {
      tail = head;
      tmp = head->next;
      head->next = nullptr;
    }
    l2 = backList(tmp);
    l1 = tmp_head;
    i = 0;
    while (i < len / 2)
    {
      auto l1_next = l1->next;
      auto l2_next = l2->next;
      l1->next = l2;
      l2->next = l1_next;
      l1 = l1_next;
      l2 = l2_next;
      i++;
    }
    l1 = tmp_head;
  }
  //链表反转
  ListNode* backList(ListNode* head)
  {
    ListNode* new_head = nullptr;
    ListNode* tmp = nullptr;
    if (!head || !head->next) return head;
    while (head)
    {
      tmp = head;
      head = head->next;

      tmp->next = new_head;
      new_head = tmp;
    }
    return new_head;
  }
};