题目：143. 重排链表
算法：
快慢指针寻找中间值翻转后半部分的链表两部分链表相加源代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if(head == nullptr){ return; } if(head->next == nullptr){ return ; } if(head->next->next == nullptr){ return ; } if(head->next->next->next == nullptr){ head->next->next->next = head->next; head->next = head->next->next; head->next->next->next = nullptr; return; } ListNode* save_head = head; ListNode* fast = head->next; ListNode* slow = head->next; //寻找中间结点 while(fast != nullptr && fast->next != nullptr){ fast = fast->next->next; slow = slow->next; if(fast ->next != nullptr){ //偶数个的时候，指向最后一个结点 if(fast->next->next == nullptr){ fast = fast->next; } } } //翻转后半部分链表 ListNode* pre = nullptr; ListNode* curr = slow->next; while(curr != nullptr){ ListNode* t = curr->next; curr->next = pre; pre = curr; curr = t; } slow->next = nullptr; //链表合并 ListNode* temp = nullptr; while(fast != nullptr){ temp = fast->next; fast->next = head->next; head->next = fast; fast = temp; head = head->next->next; } head = save_head; } };