【重点】23.合并K个升序链表-CSDN博客

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/135007267

文章介绍了两种方法来合并K个已排序的链表，分别是递归的分治策略和逐步合并的迭代方法，展示了如何在Java中实现ListNode类的merge和mergeKLists函数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

法1：分治合并

在这里插入图片描述

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0:
            return None
        elif len(lists) == 1:
            return lists[0]
        n = len(lists)
        leftNode = self.mergeKLists(lists[:n//2])
        rightNode = self.mergeKLists(lists[n//2:])

        return self.merge2Lists(leftNode, rightNode)
    
    def merge2Lists(self, leftNode, rightNode):
        dummy = ListNode(-1)
        cur = dummy
        cur1, cur2 = leftNode, rightNode
        while cur1 and cur2:
            if cur1.val <= cur2.val:
                cur.next = cur1
                cur1 = cur1.next
            else:
                cur.next = cur2
                cur2 = cur2.next
            cur = cur.next
        cur.next = cur1 if cur1 else cur2
        return dummy.next

Java

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l > r) {
            return null;
        }
        if (l == r) {
            return lists[l];
        }
        int mid = l + (r - l) / 2;
        return merge2List(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode merge2List(ListNode first, ListNode second) {
        ListNode dummy = new ListNode(-1);
        ListNode tmp = dummy;
        while (first != null && second != null) {
            if (first.val <= second.val) {
                tmp.next = first;
                first = first.next;
            } else {
                tmp.next = second;
                second = second.next;
            }
            tmp = tmp.next;
        }
        if (first == null) {
            tmp.next = second;
        }
        if (second == null) {
            tmp.next = first;
        }

        return dummy.next;
    }
}

法2：其他

在这里插入图片描述

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0:
            return None
        elif len(lists) == 1:
            return lists[0]
        n = len(lists)
        head = lists[0]
        for i in range(1, n):
            head = self.merge(head, lists[i])

        return head

    def merge(self, l1, l2):
        if l1 == None:
            return l2
        elif l2 == None:
            return l1

        dummy = ListNode(-1)
        cur = dummy
        cur1, cur2 = l1, l2
        while cur1 and cur2:
            if cur1.val <= cur2.val:
                cur.next = cur1
                cur1 = cur1.next
            else:
                cur.next = cur2
                cur2 = cur2.next     
            cur = cur.next
        cur.next = cur1 if cur1 else cur2

        return dummy.next

Java

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        ListNode merged = lists[0];
        for (int i = 1; i < lists.length; ++i) {
            merged = merge(merged, lists[i]);
        }

        return merged;
    }

    public ListNode merge(ListNode first, ListNode second) {
        ListNode dummy = new ListNode(-1);
        ListNode tmp = dummy;
        while (first != null && second != null) {
            if (first.val <= second.val) {
                tmp.next = first;
                first = first.next;
            } else {
                tmp.next = second;
                second = second.next;
            }
            tmp = tmp.next;
        }
        if (first == null) {
            tmp.next = second;
        }
        if (second == null) {
            tmp.next = first;
        }

        return dummy.next;
    }
}