🚩[NC]2. 重排链表

🚩传送门：牛客题目

题目

将给定的单链表
重新排序为：
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

要求：空间复杂度 并在链表上进行操作而不新建链表，时间复杂度
进阶：空间复杂度 ， 时间复杂度

解题思路：模拟

1. 找到中间结点，利用快慢指针

   快指针速度是慢指针两倍，故快指针跑到链表尾巴，慢指针跑一半

2. 反转链表 [mid+1,last]

3. 将两个链表二路归并

复杂度分析

时间复杂度： ，每个结点都需要遍历

空间复杂度：，没有使用额外空间

我的代码

public class Solution {
    public static ListNode reverseList(ListNode head){
        if(head==null||head.next==null)return head;
        ListNode pre=head;
        ListNode cur=head.next;
        head.next=null;
        ListNode next=null;
        while(cur!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
    public ListNode getMid(ListNode head){
        //快慢指针
        //切割[1,2,3,4]=[1->2][4->3] [1,2,3,4,5]=[1->2][5->4->3]
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    public void reorderList(ListNode head) {
        //0.除去特殊情况 0、1、2 个结点
        if(head==null||head.next==null||head.next.next==null)return;
        //1.找到中间结点 mid , mid 将区间切分[left,mid,right]
        ListNode mid=getMid(head);
        //2.反转区间[mid+1,last]
        ListNode head2=reverseList(mid.next);
        mid.next=null;
        ListNode head1=head;
        //3.给个头节点方便操作
        ListNode pcur=new ListNode(-1);
        //4.归并
        while(head1!=null||head2!=null){
            if(head1!=null){
                pcur.next=head1;
                pcur=pcur.next;
                head1=head1.next;
            }
            if(head2!=null){
                pcur.next=head2;
                pcur=pcur.next;
                head2=head2.next;
            }
        }
        return ;
    }
}