Quick sort implementation on singly linked list in Java

Problem

Implement quick sort on singly linked list.

Solution

Worst case time complexity of quick sort is O(n^2) but it’s rare.
Quick sort follows divide and conquer approach.
Quick sort is preferred over merge sort as quick sort is an

… read the rest.

Add 2 numbers expressed as singly linked lists

Problem

Add 2 numbers which are expressed as singly linked lists. Results also should be in a linked list.

Solution

Use recursion to traverse all the way to end and compute sum while returning backwards towards the start.
Deal with

… read the rest.

Merge 2 sorted singly linked lists

Problem

Merge 2 singly linked lists which are sorted. The resultant one shall also be in sorted order.

Solution

As both the input lists are sorted, traverse through the lists, compare the heads of both the lists and form a

… read the rest.

Detecting loop in singly linked list

Problem

Identifying if there is any loop in singly linked list. Loop meaning any node connecting to one of the previous nodes.

Solution

Best solution involves 2 traversal pointers – slow pointer which hops 1 node at a times and

… read the rest.

Reverse a singly linked list

Problem

Reverse a singly linked list in linear time complexity.

Solution

Traverse through the list once and for each node assign the next pointer to the previous node.
Time complexity O(n).
Java based implementation along with unit test below

package

… read the rest.

Effective way of finding middle element in a singly linked list

Problem

Find the middle element in a singly linked list. Obvious solution is traverse through the list once to find the length of list and then find out the middle element. This takes > O(n). Objective here is to Implement … read the rest.

Swap two nodes in a singly linked list

Problem

Swap any two nodes in a singly linked list. It’s not swapping the content of the nodes but the nodes itself.

Solution

First find out the previous nodes of nodes to be swapped and then establish the links.
java

… read the rest.

Linked list

Linear data structure representing ordered sequence of elements.
Elements in it are not stored in contiguous location as arrays, rather linked through the pointers.
Advantage over array
- Dynamic size. Not fixed one as array.
- Ease of insertion or deletion which

… read the rest.