【leetcode】第143题 重排链表 3种方法求解 C++_给定一个单链表 l1→l2→ →ln 1→ln重新排列为 l1→ln→ln-1 l3→l2

题目：重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

方法1：遍历一遍链表，把结点存入栈中，然后再遍历一次链表，将栈中的结点依次插到链表前面；
当遍历到的结点或它的下一结点和栈中的结点相同时，结束插入，同时断开剩下的结点的连接
时间复杂度 O(n) 空间复杂度 O(n)

	void reorderList(ListNode* head) {
   
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
        stack<ListNode* > nodes;
        ListNode* p = head;
        while(p){
                          // 先将结点存入栈中
            nodes.push(p);
            p = p->next;
        }
        p = head;
        while(p && !nodes.empty()){
        // 将栈中的结点插到链表前面
            ListNode
1
2
3
4
5
6
7
8
9
10
11
12
13