[剑指offer专项突击版-Java解法]剑指 Offer II 026. 重排链表

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

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

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

输入: head = [1,2,3,4]
输出: [1,4,2,3]

输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

提示：

• 链表的长度范围为 [1, 5 * 104]
• 1 <= node.val <= 1000

1.根据题意,需要做三件事

2.第一件事,需要找到链表的中点,然后切割链表,我们想到快慢指针

3.第二件事,翻转第二个链表,我们想到反转链表

4.第三件事,合并两个链表,我这里使用插入的方式进行合并,把第二个链表插入到第一个链表中

class Solution {
    public void reorderList(ListNode head) {
        // 找到链表重点，分成两段
        ListNode pre = findMid(head);
        // 拆分
        ListNode sec = pre.next;
        pre.next = null;
        // 翻转链表
        sec = reverseList(sec);
        mergeList(head,sec);
    }
    public ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode pre = null;
        ListNode curr = head;
        ListNode next = head.next;
        while(curr!=null) {
            curr.next = pre;
            pre = curr;
            curr = next;
            if(next!=null) {
                next = next.next;
            }
        }
        return pre;
    }
    public void mergeList(ListNode l1,ListNode l2) {
        ListNode curr = l2;
        while(l2!=null) {
            l2 = l2.next;
            curr.next = l1.next;
            l1.next = curr;
            l1 = l1.next.next;
            curr = l2;
        }
    }
}

欢迎大佬们关注小弟的博客https://blog.csdn.net/qq_41522089