3

(Merge k Sorted Lists)

 2 years ago
source link: https://tianrunhe.wordpress.com/2012/11/04/merge-k-sorted-lists/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

(Merge k Sorted Lists)

04 Nov 2012 2 Comments

by Runhe Tian in LeetCode Tags: C++, Java, Linked List, Sorting

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Thoughts:
We start with the first list and then merge it with the second list, then the third list, so on and the so forth. For merging two sorted linked list, we use the linear merging algorithm borrowed from Merge Sort. The total complexity is O(kn).

Code (Java):

public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
ListNode head = null;
for (ListNode node : lists)
head = mergeTwoLists(head, node);
return head;
}
private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
if (head1 == null || head2 == null)
return head1 == null ? head2 : head1;
if (head1.val < head2.val) {
head1.next = mergeTwoLists(head1.next, head2);
return head1;
} else {
head2.next = mergeTwoLists(head2.next, head1);
return head2;
}
}
}

Code (C++):

class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
ListNode *head = NULL;
for(int i = 0; i < lists.size(); ++i)
head = mergeTwoLists(head, lists[i]);
return head;
}
private:
ListNode *mergeTwoLists(ListNode *head1, ListNode *head2) {
if (head1 == NULL || head2 == NULL)
return head1 == NULL ? head2 : head1;
if (head1 -> val < head2 -> val) {
head1 -> next = mergeTwoLists(head1 -> next, head2);
return head1;
} else {
head2 -> next = mergeTwoLists(head2 -> next, head1);
return head2;
}
}
};

Previous (Merge Intervals) Next (Minimum Depth of Binary Tree)

2 Comments (+add yours?)

  1. 9d2eff5ce014176a3ea8793ad06cda1d?s=48&d=identicon&r=G mike
    Dec 14, 2012 @ 05:55:26

    Dear Runhe,how to found many missing int in an array by bit operate? such as [1,5,6,8,10].

    Reply

  2. 362dd433746ee9c2de18e0a77fc0ebae?s=48&d=identicon&r=G Marius
    Feb 01, 2013 @ 16:53:33

    You can get O(N * log K) if you keep the list heads in a heap.

    Reply

Leave a Reply Cancel reply


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK