Write a function named switchEvens that swaps even-valued elements at the same index between two linked lists.
Your function is passed two parameters, references to ListNode pointers representing the front of each linked list.
You should traverse both lists, find every index where both lists store an even value (one that is divisible by 2) at that same index, and swap the nodes between the two lists.
If one list has more even values than the others, any extra ones are left unmoved.
The relative order of the elements must be preserved in both lists.
For example, if ListNode pointers named front1 and front2 point to the front of lists storing the following values:
index 0 1 2 3 4 5 6 7 8 9
front1 -> 2 -> 4 -> 3 -> 7 -> 8 -> 4 -> 6 -> 12 -> 22 -> 10 /
front2 -> 66 -> 55 -> 16 -> 43 -> 22 -> 90 -> 39 -> 44 /
After the call of switchEvens(front1, front2); , the lists should store the following elements:
front1 -> 66 -> 4 -> 3 -> 7 -> 22 -> 90 -> 6 -> 44 -> 22 -> 10/
front2 -> 2 -> 55 -> 16 -> 43 -> 8 -> 4 -> 39 -> 12 /
Notice that at indexes 0, 4, 5, and 7, both lists contained an even value.
Such values were swapped between the two lists.
Your function should work properly for a list of any size, including either list being null.
Note that the goal of this problem is to modify the list by modifying pointers.
It might be easier to solve it in other ways, such as by changing nodes' data values or by rebuilding an entirely new list, but such tactics are forbidden.
Constraints:
Do not modify the data field of any nodes; you must solve the problem by changing links between nodes and adding newly created nodes to the list.
Do not create any new nodes by calling new ListNode(...).
You may create as many ListNode* pointers as you like, though.
Do not use any auxiliary data structures such as arrays, vectors, queues, maps, sets, strings, etc.
Do not leak memory; if you remove nodes from the list, free their associated memory.
Your code must run in no worse than O(N) time, where N is the length of the list.
Assume that you are using the ListNode structure as defined below:
struct ListNode {
int data; // value stored in each node
ListNode* next; // pointer to next node in list (nullptr if none)
}
