1、思路

• 找到单链表中点，将单链表分成两段；

• 两条链表交叉合成一条新链表。

2、代码

list_node * findMid(list_node * head)   //取得单链表的中间节点，并保证后半部分长度大于等于前半部分
{
    auto fast = head->next, slow = head;

    while (fast->next != nullptr && fast->next->next != nullptr)
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    return slow;
}

list_node * relocate(list_node * head)
{
    if (head == nullptr || head->next == nullptr) return head;

    auto mid = findMid(head);
    auto list1 = head, list2 = mid->next;
    mid->next = nullptr;        //断尾，切断list1尾部与list2头部的连接

    list_node *dummy = new list_node();
    auto *p = dummy;

    while (list1 != nullptr)    //list2的长度一定大于等于list1，故只需要判断list1即可
    {
        p = p->next = list1;    //交叉操作
        list1 = list1->next;

        p = p->next = list2;
        list2 = list2->next;
    }

    if (list2 != nullptr) p->next = list2;

    return dummy->next;
}