# Posts published in “List”

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)

## Solution 2: Merge Sort

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

# Problem

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list’s nodes, only nodes itself may be changed.

# Solution

Two passes.

First pass, get the length of the list.

Second pass, swap in groups.

Time complexity: O(n)

Space complexity: O(1)

# Problem

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)

# Problem

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: Brute Force

Time complexity: O(nk)

Space complexity: O(1)

# Solution 2: Heap / Priority Queue

Time complexity: O(nlogk)

Space complexity: O(k)

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

Could you do this in one pass?

# Solution 1: Two passes

Time complexity: O(L)

Space complexity: O(1)

# 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)

## Python3

Mission News Theme by Compete Themes.