# Posts published in “List”

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Solution:

1. Store the m – 1 and m-th item as prev and tail before reversing
2. Reverse the m to n, return the head and tail->next of the reversed list
3. Reconnect prev and head, tail and tail->next

Time complexity: O(n)
Space complexity: O(1)

## Python3

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)

## C++

Mission News Theme by Compete Themes.