亲宝软件园·资讯

展开

Java合并两个及以上有序链表的示例详解

Grey 人气:1

题目一:合并两个有序链表

题目链接

题目一思路

设置两个指针,一个指针(t1)指向l1链表头,另外一个指针(t2)指向l2链表头。

首先判断l1和l2的第一个元素,谁小,谁就是最后要返回的链表的头节点,如果l1和l2的第一个元素相等,随便取哪个都可以。

这样,我们就设置好了要返回链表的头节点,假设头节点是head,

依次移动t1和t2指针,谁小,谁就接入进来。依次操作,直到两个链表都遍历完毕为止。

此外,有个显而易见的结论:如果l1和l2有一个链表为空,则返回那个不为空的链表即可

题目一完整代码

public class LeetCode_0021_MergeTwoSortedLists {

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            // 如果任何一个链表为空,那么直接返回另外一个链表即可
            return l1 == null ? l2 : l1;
        }
        // 谁小谁作为头
        ListNode head = l1.val > l2.val ? l2 : l1;
        // t1 和 t2 表示l1和l2下一个要遍历的位置
        ListNode t1 = head == l1 ? l1.next : l1;
        ListNode t2 = head == l2 ? l2.next : l2;
        ListNode cur = head;
        while (t1 != null || t2 != null) {
            if (t1 == null) {
                // l1链表已经到头,剩下只需要把l2链表接入进来即可
                cur.next = t2;
                t2 = t2.next;
                cur = cur.next;
                continue;
            }
            if (t2 == null) {
                // l2链表已经到头,剩下只需要把l2链表接入进来即可
                cur.next = t1;
                t1 = t1.next;
                cur = cur.next;
                continue;
            }
            // l1和l2都没有到头,那么谁小谁接入进来即可。
            if (t1.val > t2.val) {
                cur.next = t2;
                t2 = t2.next;
            } else {
                cur.next = t1;
                t1 = t1.next;
            }
            cur = cur.next;
        }
        return head;
    }
}

题目二:合并多个有序链表

23. Merge k Sorted Lists

题目二关键思路

准备一个小根堆,并把每个链表的头节点加入到小根堆中,此时,小根堆堆顶弹出的节点一定是最后生成链表的头节点。

假设链表为:L1,L2...LN

第一步,先将L1,L2...LN的头节点L1H,L2H...LNH加入小根堆

第二步,从小根堆堆顶弹出一个元素,作为最后链表的头节点。

第三步,第二步中弹出节点所在的链表假设是i号链表,那么就找弹出节点的下一个位置(假设为X)再和小根堆堆顶元素比较:

如果X比堆顶元素大,则堆顶元素弹出,X进入小根堆

如果X比堆顶元素小,则直接不需要进入堆顶,作为结果链表

题目二完整代码

public class LeetCode_0023_MergeKSortedLists {

    public static class ListNode {
        int val;
        ListNode next;
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (null == lists || lists.length == 0) {
            return null;
        }
        if (1 == lists.length) {
            return lists[0];
        }
        // 小根堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        for (ListNode list : lists) {
            if (null != list) {
                queue.add(list);
            }
        }
        ListNode res = queue.poll();
        ListNode head = res;
        while (!queue.isEmpty()) {
            if (res != null) {
                ListNode n = res.next;
                if (n == null) {
                    res.next = queue.poll();
                    res = res.next;
                } else if (n.val > queue.peek().val) {
                    res.next = queue.poll();
                    res = res.next;
                    queue.add(n);
                } else {
                    res = res.next;
                }
            }
        }
        return head;
    }
}

加载全部内容

相关教程
猜你喜欢
用户评论