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.
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
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.
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
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.