算法--排序奇升偶降链表

摘要：链表相关的面试题，涉及链表排序、链表翻转、链表拆分

---

前言：给定一个奇数位升序，偶数位降序的链表，将其重新排序。

输入: 1->8->3->6->5->4->7->2->NULL

输出: 1->2->3->4->5->6->7->8->NULL

---

解题思路

第一步：根据奇偶顺序，将链表拆分成两个链表

第二步：将偶链表，翻转，变成升序链表(这部分可以优化，在第一步拆分链表时，就将链表翻转)

第三步：排序两个链表

leetcode 类似题目：

奇偶链表

反转链表

合并两个有序链表

解题代码

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; }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

public class Main01 {

    public static void main(String[] args) {
        // 1->8->3->6->5->4->7->2->NULL
        ListNode listNode = new ListNode(1, new ListNode(8,
                new ListNode(3, new ListNode(6, new ListNode(5, new ListNode(4,
                        new ListNode(7, new ListNode(2))))))));
        sortList(listNode);
    }

    public static ListNode sortList(ListNode root) {
        ListNode rootNode = new ListNode(root.val, root.next);
        ListNode leftRoot = null;
        ListNode leftTemp = new ListNode();
        ListNode rightRoot = null;
        ListNode rightTemp = new ListNode();

        boolean flag = true;
        int len = 0;
        // 分成两个链表
        while (rootNode != null) {
            if (flag) {
                // 找出奇数链表
                if (leftRoot == null) {
                    leftTemp.val = rootNode.val;
                    leftRoot = leftTemp;
                } else {
                    leftTemp.next = new ListNode(rootNode.val);
                    leftTemp = leftTemp.next;
                }
            } else {
                if (rightRoot == null) {
                    rightTemp.val = rootNode.val;
                    rightRoot = rightTemp;
                } else {
                    // 找出偶数链表并翻转链表
                    rightRoot = new ListNode(rootNode.val, rightTemp);
                    rightTemp = new ListNode();
                    rightTemp.val = rightRoot.val;
                    rightTemp.next = rightRoot.next;
                }
            }
            rootNode = rootNode.next;
            flag = !flag;
            len++;
        }

        // 链表排序
        rootNode = null;
        ListNode rootTemp = new ListNode();
        while (true) {
            if (leftRoot != null) {
               int leftNum = leftRoot.val;
               if (rightRoot != null) {
                   int rightNum = rightRoot.val;
                   if (leftNum > rightNum) {
                       ListNode[] listArr = getNode(rootNode, rootTemp, rightRoot);
                       rootNode = listArr[0];
                       rootTemp = listArr[1];
                       rightRoot = rightRoot.next;
                       continue;
                   }
               }

               ListNode[] listArr = getNode(rootNode, rootTemp, leftRoot);
               rootNode = listArr[0];
               rootTemp = listArr[1];
               leftRoot = leftRoot.next;
            } else if (rightRoot != null) {
                ListNode[] listArr = getNode(rootNode, rootTemp, rightRoot);
                rootNode = listArr[0];
                rootTemp = listArr[1];
                rightRoot = rightRoot.next;
            } else {
                break;
            }
        }
        System.out.println(rootNode);
        return rootNode;
    }

    public static ListNode[] getNode(ListNode rootNode, ListNode rootTemp, ListNode transferNode) {
        int num = transferNode.val;

        if (rootNode == null) {
            rootTemp.val = num;
            rootNode = rootTemp;
        } else {
            rootTemp.next = new ListNode(num);
            rootTemp = rootTemp.next;
        }

        return new ListNode[]{rootNode, rootTemp};
    }
}

• 本文作者： th3ee9ine
• 本文链接： https://www.blog.ajie39.top/2021/11/21/排序奇升偶降链表/
• 版权声明： 本博客所有文章除特别声明外，均采用 LICENSE 下的许可协议。转载请注明出处！