DO NOT CHANGE STARTER CODE

Platform Independent Solution

Please see Syllabus for more information.

Your solution has to be platform-independent; it must run on any platforms including any online IDEs:

You solution should be free of any use of packages. Example, absolutely no

/* Java Program Example - Java Import Packages */ package YOUR_CUSTOM_PACKAGE HERE;

Your solution, regardless of how many classes it has, should be in one .java file.

Your solution has to run on any online IDEs.

If your solution fails the platform-independence criteria, you will have to resubmit work subject to the late penalty.

Your solution should be reusable, meaning it will be invoked and validated against a series of input sequentially to produce consistent outcomes like so:

Solution sol = new Solution(); sol.your_function(test_input_1...); sol.your_function(test_input_2 ...);

Problem 1

You are a software engineer working on a computer simulation project involving gas and liquid particles under various wind conditions. There are millions of particles represented as computer pixels to simulate. One of the simulations involves animating a mixture of homogeneous particles in a wind tunnel. A homogeneous mixture Links to an external site.is a solid, liquid, or gaseous mixture that has the same proportions of its components throughout any given sample.

To keep track of the particle movement throughout a simulation, you are labeling these particles with positive sequential numbers, 1, 2, 3, etc., namely gas particles from 1 through k, and liquid particles from k+1 through n, assuming there are n particles to simulate. The simulation program automatically loads them into memory using a small O(n) data structure to allow for fast O(n) insertion and retrieval. The data structure of choice is linked list (L):

Non-homogeneous List: L1>L2>L3>...>Ln1>Ln

Unfortunately your simulation requires the mixture to be initially homogeneous given the following mixing pattern:

Homogeneous List: L1>Ln>L2>Ln1>L3>Ln2>L4>...

Because you are taking Professor Su's data structure class and know something about a linked list, you decide to create a solution method for the simulation program to transform any non-homogeneous list into a homogeneous list given the above mixing pattern:

public class HW3_1 { public static void main(String[] args) { // your solution method may be tested as such, with a random linked list input Node node = new Node(1); node.next = new Node(2); node.next.next = new Node(3); node.next.next.next = new Node(4); node.next.next.next.next = null; Solution sol = new Solution(); sol.mixList(node); // list becomes homogeneous after this call. See below hint. // you may use printList(node) to print out the list content after mixing. printList(node); } public static void printList(Node head) { Node node = head; while (node.next != null) { System.out.print(node.val + "->"); node = node.next; } System.out.println(node.val + "->null"); } } class Node { int val; Node next; Node(int x) { val = x; } } /** * PURPOSE: * PARAMETERS: * RETURN VALUES: */ class Solution { public void mixList(Node head) { // YOUR CODE HERE } } 

Examples

Input: 1->2->3->4->null

Output: 1->4->2->3->null

Input: 1->null

Output: 1->null

Explanation: there's nothing to homogenize with one particle.

Input: 1->2->null

Output: 1->2->null

Explanation : there's nothing to homogenize with two particles.

Input: 1->2->3->4->5->null

Output: 1->5->2->4->3->null

Constraints and Assumptions

The input list is never empty or null.

Each linked list is singly (one direction) with a null terminator, which is not considered a particle.

The input linked list can have up to 50 particles.

These particles do NOT have to be sequentially ordered. Meaning you can have 2->1->null, or 2->3->1 as an input.

The input list can have either odd or even particles. Remember null is not considered a particle but a placeholder to terminate the list.

You will be directly modifying your input list to homogenize it. The method does not need to return anything (void).

Please use the Node class provided in the Starter Code.

Hints

You may use the printList solution from your Lab Assignment to print out the list after invoking mixList() for your own debugging purpose.

You are free to create any lists running any tests in your main() function; the above main() logic is only there for illustrative purpose.

This problem can be solved using a local Stack, O(n), to keep track of your elements in an ordered fashion for mixing.