Two linked list problems this week. Although marked “hard” by leetcode, both problems are not quite complicated.

Problems

Merge k Sorted Lists

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

Accepted code can be found here

Obviously we have an naive solution, which continuously traverse through the head of k lists and find the minimum, which require O(k) each round, when k gets bigger, this method is not very satisfying.

And the way to improve the algorithm is somewhat straight forward, that is we maintain a priority queue storing all the head nodes of lists. And in each round we retrieve the top node in the priority queue and append to the result list. And this improvement reduce the cost of each round to log(k). And the worst time complexity is O(nlog(k)) with n being the total number of nodes.

The basic algorithm would be

Input: an array of sorted list 'lists'

Define a priority queue 'pq' whose top value is the node containing smallest value.

Initialize pq with the non-null head nodes of list in 'lists'
Initialize list 'result' with an dummy head node

While pq is not empty do
    let node = pop(pq)
    append node to result
    if next(node) is not null, add it to pq

return result

Reverse Nodes in k Group

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.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For 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

Accepted code can be found here

This problem is a lot trickier. The main problem is that after the first “chunk” being reversed, how do we know where the tail node should be pointing to? It shouldn’t be the head of following chunks but the head of the reversed result.

This is basically a sign for recursion, which is what I actually did.

Reverse by k Group Recursion:

Input: List 'l' with front node 'h', Positive Integer 'k'

Define reverse(head, tail) that reverse the list from head to predecessor of tail and eventually pointing to tail.

Base Case: when length l < k, return l unmodified.

Induction Case: find the predecessor of the kth node 'tp' in the list
let next(tp) = ReverseKGroup(next(tp), k)
return Reverse(h, next(tp))

There are some subtleties in the implementation, including we select the predecessor of the tail of the chunk instead of the tail itself, since the chunk tail should pointing to the following chunks before doing reverse due to the implementation. After settle all the details of list manipulation, the problem itself is not difficult to solve.

Last

This is just a review of linked list implement by “pointers”. To be honest it’s been a while for me to touch a mutable list, thankfully the mutability doesn’t cause me too much trouble in solving the problem. But indeed the neat implementation of “reverse” takes me a while to think about :P. But anyway, playing with mutable lists is not that bad.