Top Coding Algorithms — Linked List
Linked list is a list, but with each element pointing to the next element. So in a linked list, each node contains the current value of the node and a pointer to the next node.
Like the graph shown above, the first node contains a value 2 and a pointer to the next node with value 4, and so on. So the implementation of a node would be:
With the component of node implemented, let’s implement a linked list.
So the first and most important function that a linked list need to fulfil is to append a new node to the end of the list.
To append a new node, we need to start from the first node in a linked list, moving to the end of it, and append the new element to the last node.
Probably the most popular skill you need to acquire in an coding interview of linked list. To reverse a lined list, starting from the first element, we need to reverse the pointer one by one.
For each node, we reverse the pointer to assign it to previous node.
To insert a value after a certain node, we need to break the current pointer of
node1 -> node2 and add 2 more pointer
node1 -> new_node and
new_node -> node2 .
To add an element in front of a linked list, we need to assign the new element as head and point it to current head.
Lastly, we implement a utility function to print a linked list.
ln = ListNode()
[3, 2, 4]
[1, 3, 2, 4]
[4, 2, 3, 1]