题目

 

思路

首先考虑特殊情况，链表为空，或者链表只有一个元素，此时直接返回

找到中间位置，将后半部分的链表翻转，得到新链表，将后半部分链表的节点交替插入原链表

寻找链表中间节点

使用快慢指针法

设置一个快指针，一个慢指针，初始均指向链表头节点

慢指针一次向后移动一个节点，快指针一次向后移动两个节点

当快指针移动到结尾时，慢指针指向前半条链表的最后一个节点

设置一个中间节点，中间节点为慢指针的下一个

断开前后两部分链表，慢指针的下一个指向空

原地翻转链表

设置三个变量prev，curr，next

设置循环处理全部链表中的节点，将当前元素的后继改为原链表的前驱(此时当前元素与原链表的后继断开，造成后继链表中全部节点丢失)

更新三个变量，处理下一个节点，将当前元素变为prev，将next改为当前元素，将next向后移动一个节点

当移动到最后一个元素时，把当前节点直接插入到原链表的头，更新并返回新链表的头

合并两个链表

设置新链表的尾指针，初始值设为指向第一个链表的头节点

将第一条链表的头指针设为链表中的第二个节点

先将第二个链表的头节点插入第一个链表中，尾向后移动，第二个链表的头节点向后移动

将第一个链表的第二个节点连接到尾后，尾向后移动，第一个节点指针向后移动

代码

寻找链表中间节点

传入值：链表头节点

传出值：后半部分链表的头节点

ListNode* midList(ListNode* head){ListNode* fast=head;ListNode* slow=head;while(fast->next!=nullptr&&fast->next->next!=nullptr){fast=fast->next->next;slow=slow->next;}ListNode* MidNode=slow->next;slow->next=nullptr;return MidNode;}

原地翻转链表

传入值：链表头节点

传出值：新链表头节点

ListNode* reverseList(ListNode* head){ListNode* prev=nullptr;ListNode* curr=head;ListNode* next=curr->next;while(next!=nullptr){curr->next=prev;prev=curr;curr=next;next=next->next;}curr->next=prev;prev=curr;return prev;}

交替合并两个链表

void mergeList(ListNode* list1_head,ListNode* list2_head){ListNode* newListTail=list1_head;list1_head=list1_head->next;while(list1_head!=nullptr&&list2_head!=nullptr){newListTail->next=list2_head;newListTail=newListTail->next;list2_head=list2_head->next;newListTail->next=list1_head;newListTail=newListTail->next;list1_head=list1_head->next;}newListTail->next=list2_head;}

主函数

void reorderList(ListNode* head) {if(head==nullptr||head->next==nullptr)return;ListNode* secondList=midList(head);secondList=reverseList(secondList);mergeList(head,secondList);}