Split a linked list into two lists where each list contains alternating elements from it
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}.
1. Using moveNode() function
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:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL\n"); } // 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)); newNode->data = data; newNode->next = *head; *head = newNode; } // 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) { return; } 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* a = NULL; struct Node* b = NULL; struct Node* current = source; while (current != NULL) { moveNode(&a, ¤t); // Move a node to `a` if (current != NULL) { moveNode(&b, ¤t); // Move a node to `b` } } *aRef = a; *bRef = b; } int main(void) { // input keys 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--) { push(&head, keys[i]); } struct Node *a = NULL, *b = NULL; alternatingSplit(head, &a, &b); // print both lists printf("First List: "); printList(a); printf("Second List: "); printList(b); return 0; } |
Output:
First List: 7 —> 5 —> 3 —> 1 —> NULL
Second List: 6 —> 4 —> 2 —> NULL
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } } class Main { // Helper function to print a given linked list public static void printList(String msg, Node head) { System.out.print(msg); Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } /* 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. */ public static Node[] alternatingSplit(Node source) { // Split the nodes into `a` and `b` lists Node a = null; Node b = null; Node current = source; while (current != null) { // Move a node to `a` Node newNode = current; // the front source node current = current.next; // advance the source newNode.next = a; // link the old dest off the new node a = newNode; // move dest to point to the new node if (current != null) { // Move a node to `b` newNode = current; // the front source node current = current.next; // advance the source newNode.next = b; // link the old dest off the new node b = newNode; // move dest to point to the new node } } return new Node[] { a, b }; } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 3, 4, 5, 6, 7 }; // construct the first linked list Node head = null; for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } Node[] nodes = alternatingSplit(head); // print both lists printList("First List: ", nodes[0]); printList("Second List: ", nodes[1]); } } |
Output:
First List: 7 —> 5 —> 3 —> 1 —> null
Second List: 6 —> 4 —> 2 —> null
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Function to print a given linked list def printList(msg, head): print(msg, end='') ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') ''' 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 lists may be in any order. ''' def alternatingSplit(source): # Split the nodes into `a` and `b` lists a = None b = None current = source while current: # Move a node to `a` newNode = current # the front source node current = current.next # advance the source newNode.next = a # link the old dest off the new node a = newNode # move dest to point to the new node if current: # Move a node to `b` newNode = current # the front source node current = current.next # advance the source newNode.next = b # link the old dest off the new node b = newNode # move dest to point to the new node return a, b if __name__ == '__main__': # construct the first linked list head = None for i in reversed(range(7)): head = Node(i + 1, head) first, second = alternatingSplit(head) # print both lists printList('First List: ', first) printList('Second List: ', second) |
Output:
First List: 7 —> 5 —> 3 —> 1 —> None
Second List: 6 —> 4 —> 2 —> None
2. Using Dummy Nodes
Here 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:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL\n"); } // 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)); newNode->data = data; newNode->next = *head; *head = newNode; } // 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) { return; } 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) { struct Node aDummy; struct Node* aTail = &aDummy; // points to the last node in `a` aDummy.next = NULL; struct Node bDummy; struct Node* bTail = &bDummy; // points to the last node in `b` bDummy.next = NULL; struct Node* current = source; while (current != NULL) { moveNode(&(aTail->next), ¤t); // add at `a` tail aTail = aTail->next; // advance the `a` tail if (current != NULL) { moveNode(&(bTail->next), ¤t); bTail = bTail->next; } } *aRef = aDummy.next; *bRef = bDummy.next; } int main(void) { // input keys 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--) { push(&head, keys[i]); } struct Node *a = NULL, *b = NULL; alternatingSplit(head, &a, &b); // print both lists printf("First List: "); printList(a); printf("Second List: "); printList(b); return 0; } |
Output:
First List: 1 —> 3 —> 5 —> 7 —> NULL
Second List: 2 —> 4 —> 6 —> NULL
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } Node() {} } class Main { // Helper function to print a given linked list public static void printList(String msg, Node head) { System.out.print(msg); Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } /* 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. */ public static Node[] alternatingSplit(Node source) { Node aDummy = new Node(); Node aTail = aDummy; // points to the last node in `a` aDummy.next = null; Node bDummy = new Node(); Node bTail = bDummy; // points to the last node in `b` bDummy.next = null; Node current = source; while (current != null) { // add at `a` tail Node newNode = current; current = current.next; newNode.next = aTail.next; aTail.next = newNode; aTail = aTail.next; // advance the `a` tail if (current != null) { // add at `b` tail newNode = current; current = current.next; newNode.next = bTail.next; bTail.next = newNode; bTail = bTail.next; // advance the `b` tail } } return new Node[] { aDummy.next, bDummy.next }; } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 3, 4, 5, 6, 7 }; // construct the first linked list Node head = null; for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } Node[] nodes = alternatingSplit(head); // print both lists printList("First List: ", nodes[0]); printList("Second List: ", nodes[1]); } } |
Output:
First List: 1 —> 3 —> 5 —> 7 —> null
Second List: 2 —> 4 —> 6 —> null
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Helper function to print a given linked list def printList(msg, head): print(msg, end='') ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') ''' 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 lists may be in any order. ''' def alternatingSplit(source): aDummy = Node() aTail = aDummy # points to the last node in `a` aDummy.next = None bDummy = Node() bTail = bDummy # points to the last node in `b` bDummy.next = None current = source while current: # add at `a` tail newNode = current current = current.next newNode.next = aTail.next aTail.next = newNode aTail = aTail.next # advance the `a` tail if current: # add at `b` tail newNode = current current = current.next newNode.next = bTail.next bTail.next = newNode bTail = bTail.next # advance the `b` tail return aDummy.next, bDummy.next if __name__ == '__main__': # construct the first linked list head = None for i in reversed(range(1, 8)): head = Node(i, head) first, second = alternatingSplit(head) # print both lists printList('First List: ', first) printList('Second List: ', second) |
Output:
First List: 1 —> 3 —> 5 —> 7 —> None
Second List: 2 —> 4 —> 6 —> None
3. Using Recursion
We can easily solve this problem by recursion as well. The recursive implementation can be seen below in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL\n"); } // 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)); newNode->data = data; newNode->next = *head; *head = newNode; } // Recursive function to split a given linked list into two lists where // each list containing alternating elements from the original list. // The solution maintains the same order as the source list void alternatingSplit(struct Node* odd, struct Node* even) { if (odd == NULL || even == NULL) { return; } if (odd->next) { odd->next = odd->next->next; } if (even->next) { even->next = even->next->next; } alternatingSplit(odd->next, even->next); } /* 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 split(struct Node* source, struct Node** aRef, struct Node** bRef) { if (!source) { return; } *aRef = source; *bRef = source->next; alternatingSplit(*aRef, *bRef); } int main(void) { // input keys 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--) { push(&head, keys[i]); } struct Node *a = NULL, *b = NULL; split(head, &a, &b); // print both lists printf("First List: "); printList(a); printf("Second List: "); printList(b); return 0; } |
Output:
First List: 1 —> 3 —> 5 —> 7 —> NULL
Second List: 2 —> 4 —> 6 —> NULL
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } } class Main { // Helper function to print a given linked list public static void printList(String msg, Node head) { System.out.print(msg); Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Recursive function to split a given linked list into two lists where // each list containing alternating elements from the original list. // The solution maintains the same order as the source list public static void alternatingSplit(Node odd, Node even) { if (odd == null || even == null) { return; } if (odd.next != null) { odd.next = odd.next.next; } if (even.next != null) { even.next = even.next.next; } alternatingSplit(odd.next, even.next); } /* 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. */ public static Node[] alternatingSplit(Node source) { if (source == null) { return new Node[] {null, null}; } Node aRef = source; Node bRef = source.next; alternatingSplit(aRef, bRef); return new Node[] { aRef, bRef }; } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 3, 4, 5, 6, 7 }; // construct the first linked list Node head = null; for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } Node[] nodes = alternatingSplit(head); // print both lists printList("First List: ", nodes[0]); printList("Second List: ", nodes[1]); } } |
Output:
First List: 1 —> 3 —> 5 —> 7 —> null
Second List: 2 —> 4 —> 6 —> null
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Helper function to print a given linked list def printList(msg, head): print(msg, end='') ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Recursive function to split a given linked list into two lists where # each list containing alternating elements from the original list. # The solution maintains the same order as the source list def alternatingSplit(odd, even): if odd is None or even is None: return if odd.next: odd.next = odd.next.next if even.next: even.next = even.next.next alternatingSplit(odd.next, even.next) # Given the source list, split its nodes into two shorter lists. def split(source): if not source: return None, None (aRef, bRef) = (source, source.next) alternatingSplit(aRef, bRef) return aRef, bRef if __name__ == '__main__': # construct the first linked list head = None for i in reversed(range(7)): head = Node(i + 1, head) first, second = split(head) # print both lists printList('First List: ', first) printList('Second List: ', second) |
Output:
First List: 1 —> 3 —> 5 —> 7 —> None
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.
Exercise: Modify the solution to use “local references” technique to get rid of the dummy nodes.
Source: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)