Reorder List

## 一.题目描述  ## 二.题目分析 直接按照题目的要求求解，设ListNode *head为待处理的链表，算法包括以下步骤：  1\. 将链表head分为前后两部分，前半部分链表head1 和后半部分链表head2；  2\. 将后半段链表head12做逆序操作；  3\. 合并head1, head2； ## 三.示例代码 ~~~ struct ListNode { int value; ListNode *next; ListNode(int x) : value(x), next(NULL){}; }; class Solution { public: ListNode * reorderList(ListNode *head) { if (head == NULL || head->next == NULL) return head; ListNode *slow = head; ListNode *fast = head; ListNode *cut = head; while (fast && fast->next) { cut = slow; slow = slow->next; fast = fast->next->next; } cut->next = NULL; slow = reverseList(slow); ListNode *result = mergeList(head, slow); return result; } ListNode* reverseList(ListNode *head) // 翻转链表 { if (head == NULL || head->next == NULL) return head; ListNode *prev = head; ListNode *curr = head->next; ListNode *temp = curr; prev->next = NULL; while (curr) { temp = curr->next; curr->next = prev; prev = curr; curr = temp; } return prev; } ListNode* mergeList(ListNode *head1, ListNode *head2) { ListNode* temp1 = head1; ListNode* temp2 = head2; ListNode* pMerge = head1; bool flag = true; while (temp1 != NULL && temp2 != NULL) { if (flag && temp2 != NULL) { temp1 = head1->next; head1->next = temp2; head1 = head1->next; flag = false; } if (!flag && temp1 != NULL) { temp2 = head1->next; head1->next = temp1; head1 = head1->next; flag = true; } } return pMerge; } }; ~~~ 测试结果：  **四.总结** 这道题需要对链表进行翻转操作&对两个链表进行合并操作，实现本身不难，但代码只是随便一写，比较繁琐，需要后期再优化。