Given a linked list of integers, split it into two lists containing alternating elements from the original list. For example, if the original list is {1, 2, 3, 4, 5}, then one sublist should be {1, 3, 5} and the other should be {2, 4}. The elements in the output lists may be in any order. i.e., the sublists can be {5, 3, 1} and {4, 2} for input list {1, 2, 3, 4, 5}. Practice this problem The simplest approach iterates over the source list and use moveNode() to pull nodes off the source and alternately put them on a and b. The only strange part is that the nodes will be in the reverse order in the source list. The algorithm can be implemented as follows in C, Java, and Python:
// Helper function to print a given linked list void printList(struct Node* head) printf("%d —> ", ptr->data); // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Function takes the node from the front of the source and moves it // to the front of the destination void moveNode(struct Node** destRef, struct Node** sourceRef) // if the source list empty, do nothing if (*sourceRef == NULL) { struct Node* newNode = *sourceRef; // the front source node *sourceRef = (*sourceRef)->next; // advance the source pointer newNode->next = *destRef; // link the old dest off the new node *destRef = newNode; // move dest to point to the new node Given the source list, split its nodes into two shorter lists. If we number the elements 0, 1, 2, then all the even elements should go in the first list and all the odd elements in the second. The elements in the new lists may be in any order. void alternatingSplit(struct Node* source, struct Node** aRef, struct Node** bRef) // Split the nodes into `a` and `b` lists struct Node* current = source; moveNode(&a, ¤t); // Move a node to `a` moveNode(&b, ¤t); // Move a node to `b` int keys[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(keys)/sizeof(keys[0]); // construct the first linked list struct Node* head = NULL; for (int i = n-1; i >= 0; i--) { struct Node *a = NULL, *b = NULL; alternatingSplit(head, &a, &b); Download Run Code Output:
Download Run Code Output:
Download Run Code Output: Second List: 6 —> 4 —> 2 —> None 2. Using Dummy NodesHere is an alternative approach that builds the sublists in the same order as the source list. The code uses temporary dummy header nodes for the a and b lists as they are being built. Each sublist has a “tail” pointer that points to its current last node – that way, new nodes can be appended at the end of each list easily. The dummy nodes give the tail pointers something to point to initially. The dummy nodes are efficient in this case because they are temporary and allocated in the stack. Following is the C, Java, and Python implementation of the idea:
Download Run Code Output:
Download Run Code Output:
Download Run Code Output: Second List: 2 —> 4 —> 6 —> None 3. Using RecursionWe can easily solve this problem by recursion as well. The recursive implementation can be seen below in C, Java, and Python:
Download Run Code Output:
Download Run Code Output:
Download Run Code Output: Second List: 2 —> 4 —> 6 —> None The time complexity of both above-discussed methods is O(n), where n is the length of the linked list. The iterative version doesn’t require any extra space, whereas the recursive version use stack space proportional to the lists’ length. |