[数据结构与算法][leetcode篇]重排链表

??问题描述：

??算法思想：

🥇题目解读：

1. 我们看看此题，是不是 起先一点思路都没有呀！！！其实此题并不难，关键在于我们一定要读懂题目，题目是这样把链表后半段的val值，移到链表的前半段，并且是这样的 前半段的一个节点 ，后半段一个节点 ，前半段一个节点·····

🥇具体解析：

1. 首先链表分为两半，利用快慢指针思想，快指针一次遍历链表中的两个节点，慢指针一次遍历链表中一个节点，当快指针把链表遍历完时，慢指针恰好指向链表的中间节点。然后把中间节点之后的链表断开，生成两个子链表。
2. 翻转中间节点之后的链表，因为在题目中从后向前遍历链表把后半段的链表节点插入到前半段节点中,在这里翻转链表的具体步骤不加以赘述，详细请看博客链表习题
3. 翻转链表之后，例如看图说话中，链表后半段节点的顺序就变成6,5,4,最后从链表的前半段链表和后半段链表的节点开始，逐个把他们的节点相连成为一个新的链表。首先把先半段链表和后半段链表的头节点1和6连接起来，在把处于在第二个位置节点的2和5连接起来，最后把两个尾节点连接3和4起来因此最后的链表节点顺序为1,6,2,5,3,4。
4. 如果原链表的个数为奇数时，前半段链表比后半段链表多一个节点，所以说在两个子链表等分连接完成后，前半段链表还不能为空，所以在连接的链表之后添上多出的节点。

🥇看图说话：

💯代码实现：

//翻转链表
 public Node reverseList(Node node){
            Node newhead = null;
            Node cur = node;
            while(cur!=null){
                //保存节点
                Node curNext = cur.next;
                cur.next = newhead;
                newhead = cur;
                cur = curNext;
            }
            return newhead;
        }
        public Node reorderList() {
            //首先设置快慢指针，快慢指针遍历链表，慢指针一次遍历一个节点，快指针一次遍历两个节点，所以说当快指针把链表遍历
          //完时，慢指针刚好走到了链表的一半
            Node dummy = new Node(0);
            dummy.next = head;
            Node fast = dummy;
            Node slow = dummy;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            //找到中间节点，然后从中间断开链表
            Node temp = slow.next;
            slow.next = null;

           return  reSortList(head,  reverseList(temp),dummy);
        }
        public Node reSortList(Node node1,Node node2,Node head){
            Node prev = this.head;
            while(node1 != null && node2 != null){
            //保存遍历节点
                Node temp = node1.next;
                prev.next = node1; //node2节点连接node1节点
                node1.next = node2;//node1节点连接node2节点
                prev = node2;// 更新prev
                
                //遍历子链表
                node1 = temp;
                node2 = node2.next;
            }
            //如果原链表节点个数为奇数时
           if(node1!=null){
               prev.next = node1;
           }
            return head;
        }