举例：
1->2->3->4->5->6->7->8要求重排为：
1->8->2->7->3->6->4->5看似摸不着头绪，单链表的最大问题不就是没法走回头路吗？
但如果我们将链表切成两部分呢？
1->2->3->4
5->6->7->8然后回忆一下链表基本操作，咦，是否将第二个链表逆序一下即可？
1->2->3->4
8->7->6->5到了这一步，差不多真相大白了吧。两个链表合并，貌似没一点难度。
具体技术
逆序的技巧不需多说，切成两部分，关键是找中点，这个可以利用我们常用的技巧：快慢指针。
1->2->3->4->5->6->7->8->null
^ ^ ^ ^ ^ ^ ^ ^ ^
s f | | | | | | |
s | f | | | | | |
s | f | | | | |
s | | f | | | |
s | f | | |
s | f | |
s f |
s f可以看到，s 正好停在指向 4
的地方。
逆序之后，链表应呈现以下情形：
1->2->3->4->8->7->6->5->null
^ ^
head slow再进一步，将该链表分为两个：
1->2->3->4->null
8->7->6->5->null然后用咱们现成的 shuffleMerge 即可。
#include <cstddef>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
ListNode* reverseList(ListNode *head) {
ListNode *newHead = NULL;
while (head) {
ListNode *next = head->next;
head->next = newHead;
newHead = head;
head = next;
}
return newHead;
}
ListNode *shuffleMerge(ListNode *a, ListNode *b) {
ListNode *ret = NULL, **lastRef = &ret;
while (a && b) {
moveNode(lastRef, &a);
lastRef = &((*lastRef)->next);
moveNode(lastRef, &b);
lastRef = &((*lastRef)->next);
}
*lastRef = a ? a : b;
return ret;
}
void moveNode(ListNode **destRef, ListNode **sourceRef) {
ListNode *newNode = *sourceRef;
*sourceRef = newNode->next;
newNode->next = *destRef;
*destRef = newNode;
}
public:
void reorderList(ListNode *head) {
if (head == NULL) return;
ListNode *slow = head, *fast = head->next;
while (fast) {
fast = fast->next;
if (fast) {
slow = slow->next;
fast = fast->next;
}
}
ListNode *back = reverseList(slow->next);
slow->next = NULL;
head = shuffleMerge(head, back);
}
};