Category Archives: Linked list

Alternate arrangement of two linked lists

Given two linked lists, we have to merge them into a single list by alternatively taking one node from each list.We should do this by re-arranging the links and should not create duplicate nodes while merging.

For example consider the two lists

1 -> 2 -> NULL
3 -> 4 -> NULL

The result should look like the following.

1 -> 3 -> 2 -> 4 -> NULL.

There is no logic required for this problem except arranging the links carefully. 

Just take two pointers to the two lists, keep adding the first node followed by the second node by advancing both the pointers at a time. 

Come out from the loop when we reach the end of any list.

Lastly copy the remaining nodes from the longer list to the result list.

Below is the C++ implementation of the same. The program can be run through the following test cases.

  1. Two empty lists
  2. One empty list and the other non-empty list
  3. Two lists are of equal length
  4. Two lists are of unequal length

Reversing a linked list in groups of given size

Given a single linked list, and an integer k, we need to reverse the linked list in groups of size k.
For example consider the following diagram of input and output linked lists for k = 3.

There are no tricks involved in the solution for this problem. It is just an implementation challenge where we have to carefully manipulate pointers to achieve the desired result.

Here is the strategy. The first step is to subdivide the list into chunks of size k. The last chunk maybe less than size k (depends on whether the length of the linked list is a multiple of k).

Keep a reference to the beginning of the sub-list, and traverse through k nodes.
Reverse the sub-list and re-arrange the begin and end pointers for the reversed sub-list.
The following diagram might give an overview of the process.
Here is the C++ implementation including recursive as well as iterative implementation.
We can consider the following test cases to test the program.
  • An empty/NULL list
  • List with just one node
  • List with multiple of k size
  • List with non-multiple of k size
  • Arbitrary list with k = 0, k= 1, k= length(list)
  • Any combination of the above.

Deleting duplicate elements from a sorted linked list

Given a sorted linked list, how do we delete duplicate nodes from it?

This question is simple and straightforward, we take two pointers, current and next which points the adjacent nodes. In each iteration we compare the values at these two nodes, if they are equal, we delete the node pointed by next and advance the two pointers. Take a look at the following diagram to get better understanding.

Here is the C++ implementation

Splitting the linked list into two halves

Given a single linked list, how do we split it into two halves.

For example the list 1->2->3->4 should be divided into 1->2 and 3->4
If the length of the list is odd, add the extra node to first half; so 1->2->3 should be split to 1->2 and 3.

This problem can be efficiently solved using fast pointer, slow pointer mechanism explained in this post.
In this approach, the fast pointer moves two steps at a time where as the slow pointer moves one step at a time. By the time the fast pointer reaches the end of the list, slow pointer will be pointing to the end node of the first half. So we need to iterate the list only once.

Here is the C++ implementation.

Sorting a linked list using insertion sort

In one of my previous posts, we have seen how a linked list can be sorted using bubble sort approach. In this post we will see how we can sort a linked list using insertion sort algorithm. Like bubble sort this approach will also take O(n2) time.

Here is the strategy for linked list insertion sort. We maintain two lists; one sorted and another unsorted. Initially the sorted list is empty and the unsorted list will be the original list. In each iteration, we remove a node from the unsorted list and add it the sorted list in proper position. I re-used the procedure for inserting data into a sorted linked list from this post.

The following diagram should give you some understanding of the procedure.

Here is the C++ implementation of the above algorithm.

Inserting an element into sorted linked list

Given a sorted linked list write a program to insert data into it’s correct position. 
For example consider the following linked list

1 -> 3 -> 4 -> 5 

Inserting 2 should change the list to

1 -> 2 -> 3 -> 4 -> 5
Inserting 0 should change it to
0 -> 1 -> 2 -> 3 -> 4 ->5
Inserting 6 should change it to
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6. 
The three examples indicate three different cases to be considered while inserting into a sorted linked list.
Case 1: List can be empty or new element is added as the first element
Case 2: New element can be inserted anywhere in the middle of the linked list
Case 3: New element is added as the last element.

The following diagram illustrates the insert process.

In the following C++ program case 1 is handled in one block and case 2 and 3 are handled in the last block.

Pair swapping in a linked list

Given a singly linked list, we have to swap the adjacent nodes in it.
For example some input/output samples are given below
Input                              output
1->2->3->4->X                      2->1->4->3->X
1->2->3->4->5->X                   2->1->4->3->5->X
1->X                               1->X
The algorithm is very simple. We have to move pair by pair and swap the data part of each pair. 

Here is the C++ code for this.

Reverse a single linked list

Given a singly linked list, how do we reverse it by re-arranging the links?

For example if the given linked list is  1 -> 2 -> 3 -> NULL. The output of reverse method should be 3 -> 2 -> 1 -> NULL.

The following diagram shows the simple steps to perform the reversal.

And here is the C++ code which includes both recursive and iterative versions of reversal method.

Merge two sorted linked lists

Given two sorted linked lists, how do we merge them without using any extra space. That means we have to re-arrange the links to form a single sorted linked list.
For example let us consider the following two sorted lists as input.
1 -> 3 -> 5 -> 7
2 -> 4 -> 6 -> 8
The output should be
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
The algorithm is simple. We take the smaller node between the two lists in each iteration, and add it to the result list. We do this until we process any of the list to completion. If there is any remaining portion of the other list, we join it with the result list.
Here is the C++ code do this.