重排链表

方法一：暴力连接

思路：

1.观察排序后的序列我们可以发现，第一个节点后接最后一个节点，第二个节点后接倒数第二个节点，以此类推。故我们可以每次都找到最后一个节点并把它接在当前节点的后面

2.我们用一个指针p指向头节点，每次找到链表的最后一个节点并将它接在p所指节点的后面，然后p再指向下一个节点，直到p后面的节点数小于两个时停止

代码：

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        //设置一个指针p指向链表的头结点
        ListNode p=head;
        //只要p还没有指向空，即只要链表中还有节点就继续
        while(p!=null){
            //分两种情况进行分类讨论，如果p节点的后面还有两个节点，就需要去找链表 的最后
            //一个节点，将该节点从链表的尾部断开，再将该节点查到对应的p节点的后面，再更新
            //p的值，进行下一轮的查找
            //第二种情况，如果发现p节点后面没有节点了，就直接跳出，表示重排结束
            if(p.next!=null&&p.next.next!=null){
                ListNode pre=p.next;
                ListNode cur=p.next.next;
               while(cur.next!=null){
                pre=cur;
                cur=cur.next;
                }
                cur.next=p.next;
                pre.next=null;
                p.next=cur;
                p=p.next.next;  
            }else{
                break;
            }
           
        }
    }
}

方法二：线性表（对撞指针）

思路：

1.先将链表中的节点的地址存在vector中

2，再在vector的左右两边设置两个对撞指针

3.每次将两个节点进行连接

代码：

/**
 * 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) {
        //将链表中的节点的地址存在vector中
        //再设置两个对撞指针，分别指向vector的左右区间的端点
        //将左端点的节点指向右端点，再将两个小区间进行连接，更新pre
        vector<ListNode*> vec;
        ListNode *cur=head;
        while(cur!=NULL){
            vec.push_back(cur);
            cur=cur->next;
        }
        int  left=0;
        int  right=vec.size()-1;
        ListNode *pre=nullptr;
        while(left<=right){
            vec[left]->next=vec[right];
            //注意当pre指向空的时候，就不需要进行指向下一个区间
            if(pre){
                pre->next=vec[left];
            }
            pre=vec[right];
            left++;
            right--;
        }
        //不要忘记当最后pre不为nullptr的时候需要将其指向nullptr，否则会首尾相连
        if(pre){
            pre->next=nullptr;
        }
        
    
    }
};

方法三：（快慢指针、链表反转、链表交错合并）

思路：

1.先找到链表的中点，将链表一分为2

2.将链表的后半部分进行反转

3.将第一部分链表与反转后的链表交错合并

代码：

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //设置两个指针fast和slow都指向head
        //只要fast下一次走到的点不是空节点，那么就让fast两个两个节点节点走，让slow以一个节点
        //一个节点的速度走，这样由于是在同一起点出发，速度又是相差两倍，所以当fast无路可走的时候
        //slow的路程就是fast走的路程的一半，刚好到达链表的中点
    public ListNode GetMid(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    public ListNode ReverseList (ListNode  head){
        //如果发现链表是空的，就不需要进行反转
        if(head==null){
            return head;
        }
        //反转链表操作
        ListNode pre=null;
        ListNode cur=head;
        ListNode cur_next;
        while(cur!=null){
            cur_next=cur.next;
            cur.next=pre;
            pre=cur;
            //注意cur要更新成cur_next而不是cur.next!!!
            cur=cur_next;
        }
        return pre;
    }
    public void Merge(ListNode head1,ListNode head2){
        //设置四个指针，分别指向需要合并的两个链表的头结点和第二个节点
        //只要链表的前面一对节点还没有到达链表的最后，就继续
        //每次将head1指向head2，将head2指向l1
        //再更新head1和head2为l1和l2
        ListNode l1;ListNode l2;
        while(head1!=null&&head2!=null){
               l1=head1.next;
               l2=head2.next;
               head1.next=head2;
               head2.next=l1;
               head1=l1;
               head2=l2;
        }

    }
    public void reorderList(ListNode head) {
        //当链表为空的时候就不需要进行重排，直接结束
          if(head==null){
            return;
          }
          //否则就获得链表的中间的节点
          ListNode mid=GetMid(head);
          ListNode p=mid.next;
        //将中点指向null，将链表一分为二
          mid.next=null;
          ListNode t1;
          //将后半部分进行反转
          t1=ReverseList(p);
          //将链表的前半部分与后半部分交错合并
          Merge(head,t1);
        }
}