重排链表(用栈实现)

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

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

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

其他解题思路：

     这里主要讲用栈解题，其他方法也可以，比如：把链表存入数组中，再用双指针法：头—尾—头 循环便可。

用栈实现的解题思路：

    首先用快慢指针法找到链表的中间结点(如果链表个数为偶数，则找到的是左中结点)

    快慢指针法：p和q都指向第一结点，然后p向后移动两步，q移动一步。p的下一个或下下一个为空时停止，q就到中结点了。(代码则不是或而是和，因为最后一个结点指向空!)

    然后把后一半的结点存入栈中，然后让前一半的第一个结点指向栈顶元素，然后循环便可，直到栈为空。

// 代码实现

// 无注释版

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==NULL||head->next==NULL||

       head->next->next==NULL)

       return ;

    ListNode* p=head;

    ListNode* q=head;

    while(p->next!=NULL&&

          p->next->next!=NULL) {

        p=p->next->next;

        q=q->next;

    }

    p=q;

    q=q->next;

    stackstk;

    while(q!=NULL) {

        stk.push(q);

        q=q->next;

    }

    p->next=NULL;

    p=head;

    while(!stk.empty()) {

        stk.top()->next=p->next;

        p->next=stk.top();

        stk.pop();

        p=p->next->next;

    }

    }

};

// 注释版

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==NULL||head->next==NULL||
       head->next->next==NULL)
       return ;

// 双指针法令q指向中结点或左中结点

    ListNode* p=head;
    ListNode* q=head;
    while(p->next!=NULL&&
          p->next->next!=NULL) {
        p=p->next->next;
        q=q->next;
    }

    p=q;    // 令p指向前半链表的最后一个结点
    q=q->next;   // 令q指向后半链表的第一结点

// 创建栈并把后半链表按顺序存入栈中

    stackstk;   
    while(q!=NULL) {
        stk.push(q);
        q=q->next;
    }

    p->next=NULL;    // 切断前后链表
    p=head;    // 令p指向前半链表的第一个结点

// 让栈顶元素依次插入前半链表，实现排列

    while(!stk.empty()) {
        stk.top()->next=p->next;
        p->next=stk.top();
        stk.pop();
        p=p->next->next;
    }
    
    }
};