【算法训练-链表 七】【链表排序】：链表排序、链表的奇偶重排、重排链表

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // 1 入参判断，如果链表只剩一个节点或者空，则直接有序，到达终止条件
        if (head == null || head.next == null) {
            return head;
        }
        // 2 中间位置为慢指针的下一个节点，奇数节点链表为正中间，偶数则为另一半的开头，所以后半段一定是mid.next
        ListNode mid= findMidNode(head);
        // 3 设置后半段链表，断开前后半段链表
        ListNode newHead = mid.next;
        mid.next = null;
        // 4 合并两段有序链表
        return mergeSortList(sortInList(head), sortInList(newHead));
    }
    // 寻找链表中间节点
    private ListNode findMidNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 3 中间位置为慢指针的下一个节点，奇数节点链表为正中间，偶数则为另一半的开头
        return slow;
    }
    // 合并两个有序链表
    private ListNode mergeSortList(ListNode pHead1, ListNode pHead2) {
        // 1 入参判断
        if (pHead1 == null && pHead2 == null) {
            return null;
        }
        if (pHead1 == null) {
            return pHead2;
        }
        if (pHead2 == null) {
            return pHead1;
        }
        // 2 设置结果链表
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val <= pHead2.val) {
                p.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                p.next = pHead2;
                pHead2 = pHead2.next;
            }
            p = p.next;
        }
        // 3 如果其中一个链表为空，后续直接接另一个
        if (pHead1 == null) {
            p.next = pHead2;
        }
        if (pHead2 == null) {
            p.next = pHead1;
        }
        return dummy.next;
    }
}

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // 1 入参条件判断
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            // 只有1个节点，不用重排
            return head;
        }
        // 2 设置偶数虚拟头节点,并设定奇偶双指针
        ListNode odd = head;
        ListNode evenDummy = head.next;
        ListNode even = evenDummy;
        // 3 遍历链表，往奇数和偶数节点上补充对应节点,因为even在后边，所以要以even做判断，否则对于1-2-3-4这种情况
        //odd结束时指向null，null.next会有问题，返回仍然是null
        while (even != null && even.next != null) {
            // 奇数位断开指向偶数的指针并指向下一个奇数位
            odd.next = even.next;
            odd = odd.next;
            // 偶数位断开指向奇数的指针并指向下一个偶数位
            even.next = odd.next;
            even = even.next;
        }
        // 4 遍历完后偶数整体接到奇数后
        odd.next = evenDummy;
        return head;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        // 1 入参校验
        if (head == null || head.next == null) {
            return ;
        }
        // 2 找到链表中点，断开后半段链表，这次要找的mid要偏右一些，前半段保留偏长，这样后续交替衔接才没问题
        ListNode mid = middleNode(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        // 3 反转后半段链表
        l2 = reverse(l2);
        // 4 将反转后链表连接到原链表中
        mergeList(l1, l2);
    }
    // 交替合并两个链表
    private void mergeList(ListNode l1, ListNode l2) {
        ListNode pNext1;
        ListNode pNext2;
        // 因为两个链表仅仅相差1，所以直接交替合并即可
        while (l1 != null && l2 != null) {
            // 暂存两个链表的下一个节点
            pNext1 = l1.next;
            pNext2 = l2.next;
            // 交替衔接l1和l2
            l1.next = l2;
            l1 = pNext1;
            l2.next = l1;
            l2 = pNext2;
        }
    }
    // 寻找中间节点
    private ListNode middleNode(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;
    }
    // 反转链表
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode pNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = pNext;
        }
        return pre;
    }
}