前言

链表操作主要在于断链+合并。常用的重要思想是bottom-to-up + dummy。

一、案例

1）链表排序
在这里插入图片描述

2）链表合并
在这里插入图片描述

二、题解

1）链表排序

package com.xhu.offer.offerII;

public class SortList {
    //自底向上进行归并，两个链表合并为升序链表天生不需要O(n),只需一个dummyNode
    public ListNode sortList(ListNode head) {
        //自底向上进行断链
        ListNode p = head;
        int len = 0;
        while (p != null) {
            len++;
            p = p.next;
        }
        ListNode dummyHead = new ListNode(0, head);
        ListNode pre = dummyHead;
        for (int i = 1; i < len; i <<= 1) {
            ListNode cur = head;
            //开始以步长为i来断链并排序合并
            while (cur != null) {
                ListNode l1 = cur;
                int count = 1;
                while (count++ < i && cur.next != null) cur = cur.next;
                ListNode l2 = cur.next;
                cur.next = null;
                cur = l2;
                count = 1;
                while (count++ < i && cur != null) cur = cur.next;
                //记录下一组链表合并的开始，但是需判断是否到末尾了。
                ListNode next = null;
                if (cur != null) {
                    next = cur.next;
                    cur.next = null;
                }

                l1 = merge(l1, l2);
                pre.next = l1;
                while (l1.next != null) l1 = l1.next;
                pre = l1;

                cur = next;
            }
        }
        return dummyHead.next;
    }

    //返回合成链表的头节点
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(0);
        ListNode cur = dummyNode;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dummyNode.next;
    }

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

2）链表合并

package com.xhu.offer.offerII;

//合并链表
public class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        int len = lists.length;
        //自底向上两两合并
        for (int step = 1; step < len; step <<= 1) {
            for (int i = 0; i < len - step; i += 2 * step) {
                ListNode head = merge(lists[i], lists[i + step]);
                lists[i] = head;
            }
        }
        return lists[0];
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;

        for (; l1 != null && l2 != null; cur = cur.next) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
                continue;
            }
            cur.next = l2;
            l2 = l2.next;
        }
        cur.next = l1 != null ? l1 : l2;

        return dummyHead.next;
    }

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

}