NC2 重排链表

给定head链表1->2->3->4, 重新排列为 1->4->2->3
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

方法1：利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。
时间复杂度O(N)：N是链表的结点数量，遍历链表、数组构建新链表
空间复杂度O(N)：使用额外的数组空间

方法2;寻找链表中点 + 链表逆序 + 合并链表
1、找中点的话，可以使用快慢指针。快指针一次走两步，慢指针一次走一步，当快指针走到终点的话，慢指针会刚好到中点。
如果节点个数是偶数的话，slow 走到的是左端点，利用这一点，我们可以把奇数和偶数的情况合并，不需要分开考虑。
2.链表逆序
3.合并链表
时间复杂度O(N)：N是链表的结点数量，遍历链表、重组链表
空间复杂度O(1)：使用常数级空间指针

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
	ListNode* reverseList(ListNode* head)
	{
		ListNode* prev = nullptr;
		ListNode* cur = head;
		while (cur)
		{
			ListNode* next = cur->next;
			cur->next = prev;
			prev = cur;
			cur = next;
		}
		return prev;
	}

	void reorderList(ListNode *head) {
		if (head == nullptr || head->next == nullptr || head->next->next == nullptr)//至少三个结点才能连接
			return;
		ListNode* slow = head;
		ListNode* fast = head;
		while (fast->next && fast->next->next)
		{
			slow = slow->next;
			fast = fast->next->next;
		}
		ListNode* newhead=reverseList(slow->next);//将中位数后面的进行反转
		slow->next = nullptr;
		fast = head;
		slow = newhead;
		while (slow)
		{
			ListNode* next = slow->next;
			slow->next = fast->next;
			fast->next = slow;
			fast = slow->next;
			slow = next;
		}
	}
};