(Merge k Sorted Lists)

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

2 Comments (+add yours?)

  1. 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. 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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: