Rotate linked list C implementation

Rotate Linked List

Given a singly linked list, rotate linked list by K nodes clockwise. For example:

Original list : 1->2->3->4->5->NULL  K = 2
Rotated list : 3->4->5->1->2->NULL;

List : 1->3->4->5->6->7->9->10->NULL K = 4
Rotated list: 6->7->9->10->1->3->4->5->NULL

Only aim of this problem is to see if you can understand traversal of list and pointer changes. Algorithm to rotate a list is very simple as below:

1. Traverse K nodes. Store Kth node as KthNode
2. Continue traverse till end of last node of list.
3. Now point next of last node to head of list.
4. Change head to point to next of KthNode
5. Make next node of KthNode as NULL

Implementation of above algorithm

Output

2->4->6->8->10->12->NULL K = 2
6->8->10->12->2->4->NULL

Complexity of algorithm to rotate a list is O(n) as we have to traverse the entire list once. No extra space required.

Please share your thoughts and views. We would love to hear what you have to say. Sharing is caring.

Segregate even and odd nodes of linked list

Segregate even and odd nodes of linked list

In previous post: Split linked list into two containing alternate nodes, we saw how to split two list and use last pointer reference. In this post, we will   learn to segregate even and odd nodes of linked list. There should not be any new memory allocated and only movement of nodes is allowed. Example of problem is given below:

Original list: 1->2->3->4->5->6->NULL
Even list: 2->4->6->NULL
Odd list: 1->3->5->NULL

One way to segregate even odd nodes is to move all odd nodes to either start or end of the original list and then split the linked list. Drawback of moving odd nodes at start is that we may lose order of nodes in original list. Moving to end will require one extra traversal of list and special handling of last node to preserve order of list.

Algorithm to segregate even and odd nodes of list

1. Find the end of list, call it initialEnd
2. Till first even node is found, 
   2.a move odd nodes to end
3. Set head as first even node as head of list.
4. Scan through remaining nodes of list
   4.a If node is odd, move to end
   4.b If node is even, skip it
Since this loop will work till initialEnd node, this node will not be processed in loop.
5. Save next of initialEnd, it will head of odd list
5. Special case of end node, if node is even, skip it. 
   If node is odd, move to end.

Segregate even and odd nodes implementation

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}

/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}
 
void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
 
    printf("NULL");
    printf("\n");
}
 
/* Function to insert a node at the beginning of the linked list */
void moveNodeEnd(Node** lastPtrRef, Node **sourceRef)
{
    /* New node is allocated */
    Node * newNode = *sourceRef;
 
    *sourceRef = newNode->next;
 
    newNode->next = NULL;
    /* link the old list off the new node */
    *lastPtrRef = newNode;
}
 
void splitEvenOddNodes(Node *head, Node **evenList,Node **oddList){
 
    Node * current = head;
 
    //Find the tail of list
    while(current && current->next){
    	current = current->next;
    }
 
    Node *initialEnd = current;
    Node **lastPtrRefOdd = &(initialEnd->next);
 
    //Move all nodes before first even node to end
    current = head;
    while(current && current->data%2 != 0){
    	moveNodeEnd(lastPtrRefOdd, &current);
    	lastPtrRefOdd = &((*lastPtrRefOdd)->next);
    }
 
    Node * prev;
    while(current && current != initialEnd){
    	//Even node
    	if(current->data%2 == 0){
    		//first even node
    		if(*evenList == NULL){
    			*evenList = current;
    		}
    		prev = current;
    		current = current->next;
    	}
    	else{
    		//Odd node
    		moveNodeEnd(lastPtrRefOdd, &current);
    		lastPtrRefOdd = &((*lastPtrRefOdd)->next);
    		prev->next = current ; //notice current is already advanced.
    	}
    }
 
    //Save the next node, it will be start of odd list
    *oddList = initialEnd->next;
    initialEnd->next = NULL;
 
    if(initialEnd->data%2 != 0){
    	moveNodeEnd(lastPtrRefOdd, &initialEnd);
    	lastPtrRefOdd = &((*lastPtrRefOdd)->next);
    }
}
 
/* Driver program to run above code */
int main(){
     Node * L1 = NULL;
     
     push(&L1,12);
     push(&L1,10);
     push(&L1,1);
     push(&L1,6);
     push(&L1,5);
     push(&L1,2);

     printList(L1);
    
     Node *a = NULL;
     Node *b = NULL;

     splitEvenOddNodes(L1, &a,&b);

     printList(a);
     printList(b);
 
     return 0;
}

There is another very similar solution to what is done in splitting list into two with alternate nodes. Only change will be the condition to put node into appropriate list. Below is the code.

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}
 
void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
 
    printf("NULL");
    printf("\n");
}
 
/* Function to insert a node at the beginning of the linked list */
void moveNodeEnd(Node** lastPtrRef, Node **sourceRef)
{
    /* New node is allocated */
    Node * newNode = *sourceRef;
 
    *sourceRef = newNode->next;
 
    newNode->next = NULL;
    /* link the old list off the new node */
    *lastPtrRef = newNode;
}
 
void splitEvenOddNodes(Node *head, Node **evenList,Node **oddList){
	//create start of list a;
	Node *a = NULL;
	//create start of list a;
	Node *b = NULL;
 
	Node **lastPtrRefEven = &a;
	Node **lastPtrRefOdd = &b;
 
	Node *current  = head;
	while(current){
	    //even node
	    if(current->data%2 == 0){
	        //Moving current node to even list
		moveNodeEnd(lastPtrRefEven, &current);
		lastPtrRefEven = &((*lastPtrRefEven)->next);
	    }
	    //Odd node
	    else{
		//Moving current node to odd list
		moveNodeEnd(lastPtrRefOdd,&current);
		lastPtrRefOdd = &((*lastPtrRefOdd)->next);
	    }
	}
	*evenList = a;
	*oddList = b;
}
 
/* Driver program to run above code */
int main(){
    Node * L1 = NULL;

    push(&L1,12);
    push(&L1,10);
    push(&L1,8);
    push(&L1,6);
    push(&L1,4);
    push(&L1,2);

    printList(L1);

    Node *a = NULL;
    Node *b = NULL;

    splitEvenOddNodes(L1, &a,&b);

    printList(a);
    printList(b);

    return 0;
}

Output

Original list: 2->5->6->1->10->12->NULL
Even list: 2->6->10->12->NULL
Odd list: 5->1->NULL

Complexity of code to segregate even and odd nodes is O(n) as entire list needs to be traversed once. There O(1) space complexity as no new node is being allocated and only nodes are moved.

Please share your views and suggestions. We would love to hear what you have to say. Sharing is caring.

Split linked list into two containing alternate nodes

Given a singly linked list, split it into two parts, two parts of list should contain alternate nodes of original list. This is called as alternate splitting of linked list. For example,

List :   1->2->3->4->5->6->NULL
Output 
List 1 : 1->3->5->NULL
List 2 : 2->4->6->NULL

This problem only requires traversal of linked list and maintaining one addition pointer to track other list.

Method 1: 

Scan through list and take out alternate node and put it at the start of corresponding list. In this procedure, let’s us learn how to move a node a node in linked list.

Moving a node requires two pointers, one of the nodes to be moved and other of the node, new node will be attached to. Let’s us call them source (new node) and destination pointers. Since destination and source pointers will be changing,  moveNode function will use references to pointer instead of pointers. Function prototype of MoveNode function looks like:

void moveNode(Node **destinationRef, Node **sourceRef)

What do we in moveNode function? Well, there are three basic steps:

1. Create a new pointer which points to node being referenced by source pointer.

Node * newNode = *sourceRef;

2. Move source reference to next of new node above

*sourceRef = newNode->next;

3. Change new node’s  next to point to node referenced by destination ref

newNode->next = destinationRef;

4. Finally change the destination to new node

*destinationRef = newNode;

Use above moveNode function to alternate splitting of linked list. If you look closely, moveNode function is very similar to push node function except that no new node is created, only nodes are moved around.

Algorithm to split linked into two with alternate nodes

1. Initialise two list a and b with NULL
2. Scan through all nodes of list
   2.a Move current node to list a using moveNode function
   2.b If current->next is not null, move that to list b
3. Finally set the reference to be returned.

Implementation of above algorithm

Output

Input:
7->9->1->2->3->5->NULL
Output:
3->1->7->NULL
5->2->9->NULL

Complexity of above method is O(n). No extra space complexity. Only drawback of this approach is that lists created contain nodes of original list  in reverse order. See the output.

Method 2:

To avoid above problem of reverse order of list, we can use lastPointerRef. Use of lastPtrRef is explained in detail in this post : Find intersection of two sorted linked lists.

Code to split a list using lastPtrRef


Output

Input: 
7->9->1->2->3->5->NULL
Output:
7->1->3->NULL
9->2->5->NULL

Complexity of above code to split list in alternate nodes is also O(n). However, nodes in result lists are in the same order as original list. See output.

Please share if you find something wrong, you want to contribute or any suggestion. Sharing is caring.

Sort a list with 0s,1s and 2s

Given a linked list with nodes as 0s,1s and 2s, sort the linked list: all nodes with 0s come first, then 1s and at last 2s. For example:

List : 0->1->1->0->2->2->1->2->NULL
Output : 0-.0->1->1->1->2->2->2->NULL

First method is to count number of nodes with each value, like how many nodes with data as 0, 1 and 2. Once we know count of each value, start with lowest node value 0 let’s there are n such nodes, create n nodes with value 0.  Then check number of nodes with values 1 (say m) and then create m such nodes and out at the end of list which was created with value 0. Similarly with count and value 2.

In above approach, we create new nodes which takes extra space. We can avoid wasting space by using the same nodes of list. Approach will be same  as above, only difference will be that original nodes of list will be used and no new node will be created.

Algorithm to sort a list with 0s,1s and 2s

1. Traverse original list and count number of nodes with value 0 (n1), 1 (n2) and 2 (n3)
2. Now traverse list again, fill first n1 nodes with 0, next n2 nodes with 1 and last n3 nodes with 2.


Complexity of both methods above is O(n).

Some purists will say that we should not modify the content of original nodes of list. At the same time extra space should not be used and we have to solve the problem of sorting a list of 0,1 and 2.

To achieve our goal with above given constraints, only way is to re-arrange nodes of lists. This is simple thing to do as we have only three different values. Algorithm is given below and commonly know as Dutch flag algorithm:

- when you encounter 0 move it to the start
- when you encounter 2 move it to the end.
- when you encounter 1 , simply skip it .

Code for above algorithm to sort a list with 0s,1s and 2s

Complexity of above algorithm is O(n) and space complexity is O(1).

Output

Input: 1->1->2->2->1->2->NULL
Output: 1->1->1->2->2->2->NULL

Input: 0->1->0->1->2->1->2->NULL
Output : 0->0->1->1->1->2->2->NULL

Please share if you see something wrong or any other suggestion. Sharing is caring.

Merge two linked lists alternatively

Merge two linked lists alternatively

Given two linked lists, merge one linked list into another so that each node of second list is inserted into first list at alternate positions. Problem is typical known as merge two linked lists alternatively. When you merge two lists alternatively, first node of one list becomes first node of result, first node of second list becomes second, second node of first list becomes third and so on. Example:

L1 = 3->4->6->7->NULL
L2 = 1->8->10->NULL
Result = 3->1->4->8->6->10->7->NULL

Constraint for solution is that no additional space should be used while merging two linked lists. This means, we cannot create new nodes, all we can do is to re-arrange nodes of two lists alternatively.

If list are of different lengths, one list will finish before the other, then remaining part of the bigger list should be added at the end of result.

Merge two lists alternatively : Method

In one of our previous posts, we learned how to merge two sorted linked list into one sorted linked list. In that problem, we merged two lists without any additional node being created. We will use same approach. In merge sort method in previous problem, we compare two nodes, and advance pointer of linked list that has smaller node value.

In merging two linked lists alternately, decision to advance list will be very simple : a flag. If flag is true, advance first list pointer and if flag is false, advance second list pointer. Make sure previous node added to resultant node created till now  points to newly added node.

Merge two linked lists alternatively implementation

Code is very similar to merging of two sorted linked lists and simple to understand.

Complexity of algorithm to merge two linked list alternatively is O(n+m) where n and m are length of two linked lists.

There is simpler and iterative solution to this problem too. We just need to do some trick with node pointers as shown below.

merge two linked lists alternatively

Code to iterative merge a list into another at alternate positions

Complexity is same O(n+m). Advantage of iterative method over recursive is that no implicit stack memory is used.

Please leave comment if you feel something is wrong or can be improved. Sharing is caring. Please contact us if you want to contribute to website or share an interview experience.

Flatten linked list implementation C

Flatten linked list

Consider a multi layered linked list which has two pointers, next and down pointer.  Node is connected to horizontal next node using next pointer and there is vertical linked list using down pointer. Now, problem is to combine all linked lists using down pointer into one. This process called flatten linked list. Example of linked list as shown in figure.

Flatten linked list

Question is to flatten such given linked list into one flat linked list. There are some constraints :

1. Only node at the top are connected using next pointers, i.e head of each node is connected to head of next list and so on.
2. All individual linked lists following down pointer are sorted in order
3. Finally flatten linked list should be in sorted order. So for above example, final output linked list should be:

flatten linked list example

Method to flatten linked list

Instead of solving the entire problem, we will start small. How about flattening one list? No work required there. Then take two lists and try flattening them. If we start from the end of multi-layered linked list, take last two lists, flatten and merge two last linked lists. How to merge two linked list : refer :  Merge two sorted linked list. This merge operation on two linked lists return a single list. Now, merge third last list with merged list returned by merging two linked lists previously. Repeat this merge till all sublists of original linked list are merged into one.

Two hints lead us to recursive nature of solution. First, problem is divided into smaller subproblems. These subproblems are then solved and literally merged to get solution of bigger problem. Second, same processing done on two lists (merge), only difference is lists change in each merge.

Flatten linked list implementation

Complexity of algorithm to flatten linked list is O(n log n) where n is total number of nodes across all sublists.

Please share your suggestion or write if something is wrong. Sharing is caring. If you want to contribute to website, please contact us.

Union of two linked lists implementation

Union of two linked lists

Given two sorted linked list, find union of two linked lists. Union of two linked lists means collection of all nodes which are present either of the lists only once. For example:

List 1 : 1->2->3->4->5->NULL
List 2 : 2->4->6->7->NULL
Output : 1->2->3->4->5->6->7->NULL
List 1 : 1->2->3->4->NULL
List 2 : 2->4->6->7->9->11->NULL
Output : 1->2->3->4->6->7->9->11->NULL

Methods to find union of two linked lists

Brute force method

Brute force method is to use hash. Scan first list and put all nodes in a hash. Now, scan second list. Check if current node is present in hash, if yes, skip it. If not, add it to hash. At the end, create a linked list from nodes in the hash. This linked list is union of two linked lists given as input. Brute force method works even with non sorted linked lists.

Complexity of brute force method is O(m+n) where m and n are lengths of two lists and additional space complexity of O(m+n) to store on hash.

Search method

Search method requires modification of lists. Scan each node in linked list and find node in second list. If current node is not present in second list, add it to resultant list. Once all nodes of first list are scanned, add second list at end of first linked list. This will given union of two linked list, but not in any particular order.

This method also works for non sorted linked lists, however, complexity is O(m*n).  Two methods discussed till now, will not work if lists contain duplicate nodes.

Using merge sort to find union of two lists

Use merge sort algorithm on linked list with a slight change. In merge sort of linked list, we add node to result list and then advance pointer of one of the list. To find union of two linked lists, add a special case where if nodes are equal, add node to result node and advance both lists to next pointer. Algorithm is very similar to merge sort.

1. Let a and b are two lists whose union is to be found.
2. If a is null, add b to result.
3. If b is null, add a to result
4. If a->data < b->data
   4.a Create new node temp with data as a->data
   4.b Advance a to next pointer and find union of a->next and b.
   4.c set temp->next as result of 4.b
5. If a->data > b->data, repeat 4.a to 4.c with a replaced with b
6. If a->data == b->data
   6.a same as 4.a
   6.b Advance a and b to next and find union of a->next,b->next
   6.c Set temp->next as result of 6.b
7. Return temp

Find union of two list using merge sort implementation

In implementation, there is implicit space complexity of O(m+n), to avoid that iterative implementation is handy.

Iterative method to find union of two linked lists

Complexity of algorithm to find union of two lists is O(m+n).

Here assumption is that two lists are sorted. If list are not sorted, then first sort two lists using merge sort. In that case complexity will be dominated by O(m log m) and O(n log n).

Please share if you find something wrong or something can be improved. Sharing is caring.

Intersection of two linked lists implementation

Intersection of two linked lists

Given two sorted linked lists, find intersection of two linked lists. For example:

List 1 : 1->2->3->4->5->NULL
List 2 : 2->3->5->6->NULL
Output : 2->3->5->NULL
List 1 : 1->2->3->5->NULL
List 2 : 2->5->NULL
Output : 2->5->NULL

Before going into details about solution of intersection of two linked lists problem, let’s understand how  a node can be added at the end of a list efficiently. One way to add node at end is to traverse entire linked list and add node there.

Other way is use pointer reference of last node every time a new node is added. For this technique, we use a local “reference pointer” which always points to the last pointer in the list instead of to the last node. This pointer will be used for all additions in the list. The reference pointer starts off pointing to the head pointer. Later, it points to the next field inside the last node in the list. Let’s see code and understand how it works.

Push(lastPtrRef, num); adds a new node at the last pointer. The new node becomes the last node in the list.

lastPtrRef= &((*lastPtrRef)->next); Advance the lastPtrRef to now point to the next field inside new last node — that next field is now the last pointer in the list. Below figure explains the working of above code.

intersection of two linked lists

Find intersection of two linked lists using lastPtrRef

Since we have already seen how can we add a node at the end of a list using last pointer reference, it is very easy from here on.  All we need to do is to traverse two linked lists and if nodes are same, add one of them to new list. Below code is self explanatory.

Complexity of algorithm to find intersection of two linked list using last pointer reference is O(m+n) where m and n are length of two list.

Find intersection of two linked lists recursively

If you know how to merge two sorted linked list, this solution is extension of that. If you don’t please refer : Merge two linked list.

All change that needs to be done is whenever two nodes are same, create new node and add it to new list. Algorithm is below

1. Start with head of each list
2. Compare data of nodes of two list
   2.a if data in node of first list smaller, advance first list ptr.
   2.b else advance second list ptr.
   2.c if data is equal, allocate new node with data.
3. Point next of new node to result of intersection function.
   temp->next = intersection(a->next, b->next) Advance both pointers.
4. Return new node created in step 3.

Complexity of recursive method to find intersection of two linked list is again O(m+n). However, there is implicit space complexity of O(max(m,n)) due to recursion.

Please share your thoughts, any suggestion or if you find something wrong, please leave a comment. Sharing is caring. If you are interested in contributing to website or have an interview experience to share, please contact us.

Identical linked lists: Find if two lists are equal

Identical linked lists

Given two singly linked lists, find if two linked lists are identical linked lists. For example:

List1: 1->2->3->4->5->NULL
List2: 1->2->3->4->5->NULL
Output: true

List1: 1->2->3->4->NULL
List2: 1->2->3->NULL
Output: false

Time tested method to check equality of two things is to use hash. In this case, put node values of first list in hash and look for nodes of second list. Also, make sure all elements put into hash are checked at least once.

1. Put all nodes in list 1 in hash.
2. Scan second list.
   2.a If any node in second list is not present in hash, return false.
3. If any element in hash is not checked once, then return false.
4. Return true;

Complexity is O(n+m) where n and m are length of two list. Also, space complexity will be O(n) to store n values of first linked list.

Second method is to scan both linked list simultaneously and compare nodes. Algorithm will be :

1. For all nodes in first and second list
   1.a If data of nodes is not equal, return false.
   1.b advance to next nodes in both linked lists.
2. If both linked list are finished, return true. Else return false

Identical linked list implementation

Complexity of algorithm to determine identical linked lists is O(n) with with O(1) space complexity.

Third way is to use recursion. If current nodes of two lists are equal, problem reduces to check if two sublists are identical. Base case will be to check if both lists are finished or not. Below is recursive implementation to find if two linked list are identical.

Identical linked lists : Recursive implementation

Complexity of recursive solution too is O(n), however there is an implicit space complexity O(n).

Please share if you find something wrong or suggestions. Sharing is caring. If you are interested in contributing to website or have an interview experience to share, please contact us.

Print linked list in reverse order

We have learned to traverse a singly list in forward order. What if problem is to traverse or print a singly linked list in reverse order? For example:

Link list : 1-2->3->4->5->NULL
Output should be : 5 4 3 2 1

Since, we have no way to traverse linked list in back ward direction, this becomes an interesting problem.

Brute force solution for traversing linked list in reverse order is to first reverse list, then print it and then again reverse it. Complexity of this approach is O(n). However there two caveats : First we are modifying the original input and second scanning list thrice (two times for reverse and once for printing).

Question is can we not modify list and do it in one scan?  Problem here is that last element is to be printed first, then second to last and so on till head of list is printed at last. What is the data structure which gives us such last in first out capability? Great, it’s stack!

Our second approach is to traverse linked list and put all nodes on to stack. Now print elements from stack till it is empty.  This method scans list twice  (once while putting in stack and next time when printing stack). Other problem with this approach is O(n) extra space is used.

Can we simulate stack using recursion? This will reduce scans to only once. However, there is implicit usage of O(n) space to store stack frames  of function calls. Recursive algorithm to print linked list in reverse order  :

1. If node is null, return
2. PrintList(node->next)
3. Print node->data;

Code is very simple to implement.

This may sound a very simple problem, but the technique (recursive reverse traversal of singly linked list) is used in many other problems like : Delete a linked list and Find if linked is palindrome or not.

As mentioned above, complexity of recursive method to print linked list in reverse order is O(n) with O(n) implicit space complexity. One note of caution, in production environment, one with explicit stack is preferred over recursion when size of input is unpredictable.

Please write in comments if you find something wrong or want some improvement. Sharing is caring.