[数据结构与算法] leetcode----143. 重排链表（寻找链表中点、反转链表以及链表合并合体）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> leetcode----143. 重排链表（寻找链表中点、反转链表以及链表合并合体） -> 正文阅读

[数据结构与算法]leetcode----143. 重排链表（寻找链表中点、反转链表以及链表合并合体）

143. 重排链表（寻找链表中点、反转链表以及链表合并）

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

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：

示例1：

示例2：

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

思路：寻找链表中间节点，反转后半部分链表。然后两个指针head和tail，head从前往后，tail从后往前，每一轮两个指针各走一步，走之前将tail插入到head后面，直到head或者tail指针有一个指向中间节点。

class Solution {
    public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //寻找中间节点，中间节点就是重排之后链表的最后一个节点
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        //反转后半部分链表
        ListNode cur = slow;
        ListNode prev = null;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        //重排链表，双指针，指针head从前往后，指针tail从后往前，每次都将tail指针指向的节点插入到head节点后面，直到其中一个节点遇到中间节点，结束即可
        ListNode tail = prev;
        while(head != slow && tail != slow) {
            ListNode hNext = head.next;
            ListNode tNext = tail.next;
            head.next = tail;
            tail.next = hNext;
            head = hNext;
            tail = tNext;
        }
    }
}