HackerRank: Insert a node in a double linked list

May 8, 2016


Problem statement:
https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list


Julia spent over 30 minutes to work out a solution:

https://gist.github.com/jianminchen/a9794202ddc66d25cc1d416e04adc7a9

A few of mistakes in first writing:
1. If the list is empty, add a new node, forget to return the node;
2. Insert a node, 3 possible positions:
   before the head,
   in the middle of list,
   at the end of list <-  edge case -> forget the edge case first time

Review other submissions:

Question and answer:

1. What do you learn through the study?

Julia learns to write an iterative solution for the problem. And also she fixed all the bugs and then complete the task.

The solution Julia takes is not the best one, she uses dummy head node to help, and then, use iterative solution to the do work. Need more practice.

She learned that she needs more ideas, in order to complete it in less than 10 minutes.

Also, the linked list - the simple problem is also very helpful to learn how to think recursively.

2. This is a solution to study - use recursive function, much short code, less time to write:

https://gist.github.com/jianminchen/e1e528eda506c185182a68a0df3be544

Before Julia reads the code in detail, she wrote her own recursive solution. It is fast, no dummy head need, and also much easy to read:

https://gist.github.com/jianminchen/fc0d0fc2171ed891330d5cf773c45206

Forget to add one more line: after line 30, before line 31.
(head->next)->prev=head;

Let us talk about the idea using recursive function - how to design the function? 

Test case: 2->4->6, insert a value 1, 
First, deal with the case that the list is empty: create a new node, and then return;
Second, if the inserted value is less than head's value, then create a new head with value 1, 
link it to the head; 
Otherwise, the first node is processed, and the next node of it is the value of recursive call. 
It saves time to write recursively here.


3. What are the common issues you find in the submissions?

https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list/leaderboard

--
More practice on May 9, 2016
Linked List on HackerRank:
problem statements:
https://www.hackerrank.com/domains/data-structures/linked-lists/difficulty/all/page/1

Get Node value:
https://gist.github.com/jianminchen/d4da2ec82876d93bcd1920927054702d

Reverse a doubly linked list:
https://gist.github.com/jianminchen/5bdf999c91964e87788e0d010eb52e53

Merge two sorted linked list
https://gist.github.com/jianminchen/c09df676896e938d7f6c3819e301545c

Compare two linked list:
https://gist.github.com/jianminchen/904a955b78a56ece032f5b9a681f91fc

Reverse a linked list:
https://gist.github.com/jianminchen/2c0203cebd076ae329a10e870c414219

Reverse print:
https://gist.github.com/jianminchen/91e8dfeac0e962307b30f4afd0bb6f98

Delete a node:
https://gist.github.com/jianminchen/d0a360f5a5a4be3b6d94e09d6bd0f266

Insert a node at a specific position:
https://gist.github.com/jianminchen/5b357be38d6bad427e885c7b7343c19b

Insert a node at the head of a linked list
https://gist.github.com/jianminchen/79dd121f3135769d57088c7d2e9e51fe

Insert a node at tail of a linked list
https://gist.github.com/jianminchen/957d2025fd310a9e59fb88fe8766e0de

print list
https://gist.github.com/jianminchen/cd219738d812605e0c6ced926d2e488c

Trees:
Problem statements:
https://www.hackerrank.com/domains/data-structures/trees

height of tree:
https://gist.github.com/jianminchen/18de7257b29bf6ccbab63cdc93d4077f

Top view:
problem statement:
https://www.hackerrank.com/challenges/tree-top-view
https://gist.github.com/jianminchen/f7742a123f3524c1d0fbd98e71c8f516

Level Order Traversal:
https://gist.github.com/jianminchen/a3194f885fc542a7f5827cbcdc92a3f5