花花酱 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

Problem

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Solution 0: Cheating! store the nodes in an array

C++

// Author: Huahua

class Solution {

public:

ListNode *removeNthFromEnd(ListNode *head, int n) {

if (!head) return nullptr;

vector<ListNode *> nodes;

ListNode *cur = head;

while (cur) {

nodes.push_back(cur);

cur = cur->next;

}

if (n == nodes.size()) return head->next;

ListNode* nodes_to_remove = nodes[nodes.size()-n];

ListNode* parent = nodes[nodes.size() - n - 1];

parent->next = nodes_to_remove->next;

delete nodes_to_remove;

return head;

}

};

Solution 1: Two passes

Time complexity: O(L)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode* removeNthFromEnd(ListNode* head, int n) {

int l = 0;

ListNode* cur = head;

while (cur) {

++l;

cur = cur->next;

}

if (n == l) {

ListNode* ans = head->next;

delete head;

return ans;

}

l -= n;

cur = head;

while (--l) cur = cur->next;

ListNode* node = cur->next;

cur->next = node->next;

delete node;

return head;

}

};

Solution 2: Fast/Slow Pointers + Dummy Head / Prev

Fast pointer moves n steps first, and then slow pointer starts moving.

When fast pointer reaches tail, slow pointer is n-th node from the end.

Time complexity: O(L)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode* removeNthFromEnd(ListNode* head, int n) {

ListNode* fast = head;

for (int i = 0; i < n; ++i)

fast = fast->next;

ListNode dummy(0);

dummy.next = head;

ListNode* prev = &dummy;

while (fast) {

fast = fast->next;

prev = prev->next;

}

ListNode* node = prev->next;

prev->next = node->next;

delete node;

return dummy.next;

}

};

Java

// Author: Huahua

class Solution {

public ListNode removeNthFromEnd(ListNode head, int n) {

ListNode dummy = new ListNode(0);

dummy.next = head;

ListNode fast = head;

while (n-- > 0) fast = fast.next;

ListNode prev = dummy;

while (fast != null) {

fast = fast.next;

prev = prev.next;

}

prev.next = prev.next.next;

return dummy.next;

}

Python3

# Author: Huahua

class Solution:

def removeNthFromEnd(self, head, n):

dummy = ListNode(0)

dummy.next = head

fast, prev = head, dummy

for _ in range(n):

fast = fast.next

while fast:

fast, prev = fast.next, prev.next

prev.next = prev.next.next

return dummy.next

Posts published in “List”

花花酱 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++

花花酱 LeetCode 19. Remove Nth Node From End of List

Problem

Solution 0: Cheating! store the nodes in an array

C++

Solution 1: Two passes

C++

Solution 2: Fast/Slow Pointers + Dummy Head / Prev

C++

Java

Python3