花花酱 LeetCode 23. Merge k Sorted Lists

By zxi on June 22, 2019

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

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution 1: Min heap

Time complexity: O(nklogk)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

ListNode* mergeKLists(vector<ListNode*>& lists) {

ListNode dummy(0);

ListNode *tail = &dummy;

auto comp = [](ListNode* a, ListNode* b) { return a->val > b->val; };

priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> q(comp);

for (ListNode* list : lists)

if (list) q.push(list);

while (!q.empty()) {

tail->next = q.top(); q.pop();

tail = tail->next;

if (tail->next) q.push(tail->next);

}

return dummy.next;

}

};

Solution 2: Merge Sort

Time complexity: O(nklogk)
Space complexity: O(logk)

C++

// Author: Huahua

class Solution {

public:

ListNode* mergeKLists(vector<ListNode*>& lists) {

return merge(lists, 0, lists.size() - 1);

}

private:

ListNode* merge(vector<ListNode*>& lists, int l, int r) {

if (l > r) return nullptr;

if (l == r) return lists[l];

if (l + 1 == r) return mergeTwoLists(lists[l], lists[r]);

int m = l + (r - l) / 2;

auto l1 = merge(lists, l, m);

auto l2 = merge(lists, m + 1, r);

return mergeTwoLists(l1, l2);

}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

if (l1) tail->next = l1;

if (l2) tail->next = l2;

return dummy.next;

}

};

花花酱 LeetCode 24. Swap Nodes in Pairs

By zxi on October 2, 2018

Problem

Given a linked list, swap every two adjacent nodes and return its head.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:

Your algorithm should use only constant extra space.
You may not modify the values in the list’s nodes, only nodes itself may be changed.

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode *swapPairs(ListNode *head) {

if (!head || !head->next) return head;

ListNode d(0);

d.next = head;

head = &d;

while (head && head->next && head->next->next) {

auto n1 = head->next;

auto n2 = n1->next;

n1->next = n2->next;

n2->next = n1;

head->next = n2;

head = n1;

}

return d.next;

}

};

Python3

class Solution:

def swapPairs(self, head):

if not head or not head.next: return head

dummy = ListNode(0)

dummy.next = head

head = dummy

while head.next and head.next.next:

n1, n2 = head.next, head.next.next

n1.next = n2.next

n2.next = n1

head.next = n2

head = n1

return dummy.next

Posts tagged as “list”

花花酱 LeetCode 92. Reverse Linked List II

C++

Python3

花花酱 LeetCode 23. Merge k Sorted Lists

Solution 1: Min heap

C++

Solution 2: Merge Sort

C++

花花酱 LeetCode 25. Reverse Nodes in k-Group

Problem

Solution

C++

Related Problems

花花酱 LeetCode 24. Swap Nodes in Pairs

Problem

Solution

C++

Python3

Related Problems

花花酱 LeetCode 23. Merge k Sorted Lists

Problem

Solution 1: Brute Force

C++

Solution 2: Heap / Priority Queue

C++