重排链表

       //方法一：使用双端队列
    import java.util.Deque;
    import java.util.LinkedList;
    public class Solution {
        public void reorderList(ListNode head) {    
            Deque<ListNode> list = new LinkedList<>();
            ListNode cur = head;
            while (cur != null) {
                list.add(cur);
                cur = cur.next;
            }
            boolean flag = true;
            while (list.size() > 0) {
                if (flag) {
                    list.pollFirst().next = list.peekLast();
                    flag = false;
                } else {
                    list.pollLast().next = list.peekFirst();
                    flag = true;
                }
            }
        }
    }

// 方法二：使用快慢指针+反转链表

public class Solution {

  public  void reorderList(ListNode head) {

        if (head == null)

            return;

        ListNode p1 = head;

        ListNode p2 = head.next;

        //快慢指针

        while (p2 != null && p2.next != null) {

            p1 = p1.next;

            p2 = p2.next.next;

        }



        ListNode reverse = null;

        if (p2 == null) {

            reverse = reverse(p1.next);

            p1.next = null;

        } else {

            reverse = reverse(p1);

            p1.next = null;

        }

        ListNode cur1 = head;

        ListNode cur2 = reverse;

        while (cur1 != null && cur2 != null) {

            ListNode oldNext1 = cur1.next;

            ListNode oldNext2 = cur2.next;

            cur1.next = cur2;

            cur2.next = oldNext1;

            cur1 = oldNext1;

            cur2 = oldNext2;

        }



    }



    //反转链表

    private  ListNode reverse(ListNode h) {

        ListNode p = h;

        ListNode pre = null;

        while (p != null) {

            ListNode oldNext = p.next;

            p.next = pre;

            pre = p;

            p = oldNext;

        }

        return pre;

    }



}

const int N = 1e4;

typedef struct ListNode* NodePtr;

void reorderList(NodePtr head ) {
  // corrner case
  if (!head || !head->next) return;
  
  NodePtr stk[N];
  int top = -1;
  
  NodePtr slow = head, fast = head;
  while (fast && fast->next) {
    *(stk + ++top) = slow;
    slow = slow->next;
    fast = fast->next->next;
  }
  
  NodePtr p, q = fast ? slow->next : slow, nxt;
  while (top >= 0) {
    p = *(stk + top--);
    nxt = q->next;
    q->next = p->next;
    p->next = q;
    q = nxt;
  }
  
  slow->next = NULL;
}

    public void reorderList(ListNode head) {
        if(head==null||head.next==null) return;
        ListNode pre=null;
        ListNode p=head;
        while(p.next!=null&&p.next.next!=null){
            ListNode q=p.next;
            while(q.next!=null){
                pre=q;
                q=q.next;//找到最后一个
            }
            pre.next=null;//截断
            q.next=p.next;//将q插入p之后
            p.next=q;
            p=p.next.next;//连跳两下
        }
        
    }

class Solution {
    ListNode* Rerverse(ListNode*pHead){
        ListNode*tail=pHead;
        while(tail->next)tail=tail->next;
        while(pHead!=tail){
            ListNode*temp=pHead->next;
            pHead->next=tail->next;
            tail->next=pHead;
            pHead=temp;
        }
        return tail;
    }
public:
    void reorderList(ListNode *head) {
        if(!head||!head->next)return ;    //必须考虑到只有一个节点和空节点的情况
        ListNode*fast=head,*slow=head;
        while(fast->next&&fast->next->next){    //快慢指针求中间节点
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode*pHead=slow->next;
        slow->next=nullptr;
        ListNode*p2=Rerverse(pHead);    //翻转列表    尾插法
        ListNode*p1=head;
        while(p2){
            ListNode*p=p1->next;
            p1->next=p2;
            ListNode*pp=p2->next;
            p2->next=p;
            p1=p;
            p2=pp;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        if(!head)  return;
        // 快慢指针找到中间节点
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next != NULL && fast->next->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
        }
        // 拆分链表，并反转中间节点之后的链表
        ListNode* after = slow->next;
        slow->next = NULL;
        ListNode* pre = NULL;
        while(after != NULL){
            ListNode* temp = after->next;
            after->next = pre;
            pre = after;
            after = temp;
        }
        // 合并两个链表
        ListNode* first = head;
        after = pre;
        while(first != NULL && after != NULL){
            ListNode* ftemp = first->next;
            ListNode* aftemp = after->next;
            first->next = after;
            first = ftemp;
            after->next = first;         
            after = aftemp;         
        }
    }
};

public void Solution(ListNode head){
        if(head == null) return;

        ListNode lowNode = head;
        ListNode fastNode = head;

        while(fastNode.next != null && fastNode.next.next != null){
            lowNode = lowNode.next;
            fastNode = fastNode.next.next;
        }

        ListNode leftNode = head;
        ListNode rightNode = lowNode.next;
        // 切断中间链
        lowNode.next = null;

        ListNode p = new ListNode(-1);
        ListNode returnNode = p;
        // head是左链头  rightNode是右链头
        while(leftNode != null){
            p.next = leftNode;
            leftNode = leftNode.next;

            ListNode tempR = rightNode;
            while (tempR != null && tempR.next!= null && tempR.next.next!=null){
                tempR = tempR.next;
            }
            if(tempR == null || tempR.next == null){
                p.next.next = tempR;
                rightNode = null;
            }else{
                p.next.next = tempR.next;
                tempR.next = null;
            }
            if(p.next != null){
                p = p.next.next;
            }
        }

        head = returnNode;
    }

public class Solution {
    // 快慢指针寻找链表中点
    private static ListNode findMid(ListNode head){
        ListNode quick = head;
        ListNode slow = head;
        while(quick.next!=null && quick.next.next!=null){
            quick = quick.next.next;
            slow = slow.next;
        }
        return slow;
    }
    // 链表反转
    private static ListNode reverse(ListNode head){
        ListNode rhead = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode tmp = cur;
            cur = cur.next;
            tmp.next = rhead;
            rhead = tmp;
        }
        return rhead;
    }
    
    public void reorderList(ListNode head) {
        if(head==null||head.next==null) return;
        // 找到中点后将链表分为两部分，后面一部分反转
        ListNode mid = findMid(head);
        ListNode rhead = reverse(mid.next);
        mid.next = null;
        ListNode p = head;
        ListNode q = rhead;
        // 将两截链表按照p0->q0->p1->q1...重新连接
        while(p!=null&&q!=null){
            ListNode a = p.next;
            ListNode b = q.next;
            p.next = q;
            q.next = a;
            p = a;
            q = b;
        }
    }
}

/** 递归思想
    每一次将链表尾结点取出，插入至当前链表的头结点之后
    对插入结点之后的链表（即原链表的第二个结点之后的子链表）重复上述操作
    完成排序
    */
public class Solution {
    public void reorderList(ListNode head) {
        if(head!=null && head.next!=null){
            ListNode tail;
            for(tail=head;tail.next.next!=null;tail=tail.next);
            ListNode p=tail.next;
            tail.next=null;
            p.next=head.next;
            head.next=p;
            reorderList(p.next);
        }
    }
}

public class Solution {
    public void reorderList(ListNode head) {
        if(head != null && head.next != null){
            //快慢指针找到中间节点rightHead
            ListNode p1 = head, p2 = head;
            while(p2.next != null && p2.next.next != null){
                p1 = p1.next;
                p2 = p2.next.next;
            }
            ListNode rightHead = p1.next;
            p1.next = null;
            //将右边链表逆序翻转
            p1 = rightHead.next;
            rightHead.next = null;
            while(p1 != null){
                p2 = p1.next;
                p1.next = rightHead;
                rightHead = p1;
                p1 = p2;
            }
            //leftHead 和 rightHead 拼接
            ListNode leftHead = head;
            while(rightHead != null){
                ListNode rightNext = rightHead.next, leftNext = leftHead.next;
                leftHead.next = rightHead;
                leftHead.next.next = leftNext;
                leftHead = leftNext;
                rightHead = rightNext;
            }
        }
    }
}

emmm就是把最后一个节点往插呗 简单粗暴
终止条件需要判断一下。优点是代码短，缺点是复杂度有点不妥
第一次做题一开始没考虑空链表的情况 以后注意（这让我回想到为什么我蓝桥杯明明自己运行的很好但是最后竟然没得奖）
看到很多大佬用三步走的办法 等会学习一下
感觉用队列和栈也可以做 等会也试试

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        if(head==nullptr||head->next==nullptr||head->next->next==nullptr)
            return ;
        ListNode *p,*m,*q;
        p = head;
        m = p;
        q = m;
        while(p->next!=m && p->next!=nullptr){
            m = head->next;
            while(m->next->next!=nullptr){
                m = m->next;        
            }  
            q = m->next;
            m->next = NULL;     
            q->next = p->next;
            p->next = q;    
            p = q->next;
            }
        return ;
        }
};

//解法二来啦 就是中间-翻转-合并
class Solution {
public:
    void reorderList(ListNode *head) {
        if(head==nullptr||head->next==nullptr||head->next->next==nullptr)
            return ;
        ListNode *slow,*fast;//中间
        slow = head;
        fast = head;
        while(fast->next!=nullptr&&fast->next->next!=nullptr) {// 这个判断注意顺序，一个next要写在两个next之前 
            slow = slow->next;
            fast = fast->next->next;
        }
        //printf("%d\n",slow->data);

        ListNode *m,*p;//翻转
        m = slow->next;
        while(m->next!=nullptr){
            p = m->next;
            m->next = p->next;
            p->next = slow->next;
            slow->next = p;        

        }

        ListNode *se,*fi,*tem;//合并
        se = slow->next;
        fi = head;
        slow->next = nullptr;
        while(fi!=NULL&&se!=nullptr){
            tem = se;
            se = se->next;
            tem->next = fi->next;
            fi->next = tem;        
            fi = fi->next->next;        
        }
        }
};

class Solution {
public:
    void reorderList(ListNode *head) {
        if (head == NULL || head->next == NULL || head->next->next == NULL)
            return;
        ListNode** left = &head;
        ListNode** right = left;
        while (*left != NULL && (*left)->next != NULL) {
            while (*right != NULL && (*right)->next != NULL) {
                right = &(*right)->next;
            }
            ListNode* tail = *right;
            *right = NULL;
            tail->next = (*left)->next;
            (*left)->next = tail;
            left = &(*left)->next->next;
            right = left;
        }
        return;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    
    // 快慢指针拆分链表
    ListNode* cutList(ListNode* head){
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head->next;
        // 快慢指针进行更新
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        // 切断链表并返回
        ListNode* temp = slow->next;
        slow->next = nullptr;
        return temp;
    }
    
    // 链表翻转
    ListNode* reverse(ListNode* head){
        // 特殊情况判断
        if (!head || !head->next){
            return head;
        }
        // 定义头结点、三指针
        ListNode* prehead = new ListNode(0);
        prehead->next = head;
        ListNode *last = prehead, *current = head, *next = head->next;
        // 开始进行翻转
        while(current){
            current->next = last;
            last = current;
            current = next;
            next = (next) ? next->next : nullptr;
        }
        // 进行后处理并返回
        head->next = nullptr;
        return last;
    }
    
    void relink(ListNode* head, ListNode* mid){
        ListNode *point_1 = head, *point_2 = mid;
        while(point_1){
            // 声明寄存器
            ListNode* temp = point_1->next;
            // 修改point_1指针
            point_1->next = point_2;
            point_1 = temp;
            // 判出
            if (!point_2)
                break;
            // 修改point_2指针
            temp = point_2->next;
            point_2->next = point_1;
            point_2 = temp;
        }
    }
    
public:
    void reorderList(ListNode *head) {
        if (!head || !head->next){
            return ;
        }
        // 切分list
        ListNode* mid = cutList(head);
        // 逆序第二个list
        mid = reverse(mid);
        // 重新连接list
        relink(head, mid);
    }
};