Question

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: L 1 − > L 2 − > L 3 − > . . . − > L n − 1 − > L n

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

Homogeneous List: L 1 − > L n − > L 2 − > L n − 1 − > L 3 − > L n − 2 − > L 4 − > . . .

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 HomeworkAssignment3_1 {    
    public static void main(String[] args) {
       // just like any problems, whatever you need here, etc. For example:
        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 be homogeneous after this call
    }
}
class Node {
    int val;
    Node next;
    Node(int x) { val = x; }
}
// YOUR API DOCUMENTATION GOES HERE
class Solution {
    // OR, YOUR API DOCUMENTATION CAN GO HERE TOO
    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.
• 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.

HINTS

• You may use the printList solution from your LabAssignment 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.
• You can use the following solution method to visualize your list of choice:

public 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");
}

Answer 1

/* Java code fro rearranging the linkedlist */

import java.util.*;
class RearrangeLinkedList
{
   public static void main(String args[])
   {
       Node head=createLL();
       System.out.println("Before rearranging LinkedList is as follows");
       printLL(head);
       rearrangeLL(head);
       System.out.println("After rearranging LinkedList is as follows");
       printLL(head);
   }
   // method that rearranges the linkedlist as given in question
   public static void rearrangeLL(Node head)
   {
       Node middleNode=getMiddleNode(head);                   // middleNode points to middle node of linkedlist
       Stack<Node> stack=new Stack<Node>();
       for(Node node=middleNode.link;node!=null;node=node.link)
       {
           stack.add(node);                                   // store all elements from next of middleNode in stack
       }  
       middleNode.link=null;                                   // make middleNode.link as null as it is the last node after rearranging
       Node node=head;
       while(node!=null && !stack.isEmpty())  
       {
           Node temp=stack.pop();                               // take top most element from stack and add it to front
           temp.link=node.link;
           node.link=temp;
           node=node.link.link;                               // update link accordingly
       }
   }
   // method that prints the linked list
   public static void printLL(Node head)
   {
       for(;head!=null;head=head.link)
           System.out.print(head.data+"->");
       System.out.println("null");
   }
   // method that returns middleNode pointer
   public static Node getMiddleNode(Node head)
   {
       Node middleNode=head;                                   // middleNode and node initially points to head node of linkedlist
       Node node=head;
       int count=0;                                           // maintain the count of linkedlist
       while(node!=null)
       {
           if( (count & 1) == 1 )                               // if the current node count is odd, then update middleNode to its next node
               middleNode=middleNode.link;
           count++;                                           // increment count and update node
           node=node.link;
       }                                                       // finally middle node address is stored in middleNode variable
       return middleNode;                                       // return middleNode
   }
   // method that creates a new LinkedList and returns the head
   public static Node createLL()
   {
       Node head=new Node(1);
       head.link=new Node(2);
       head.link.link=new Node(3);
       head.link.link.link=new Node(4);
       head.link.link.link.link=new Node(5);
       return head;
   }
}
class Node
{
   int data;
   Node link;
   Node(int data)
   {
       this.data=data;
   }
}

Output is as follows for above created linkedlist:

Before rearranging LinkedList is as follows
1->2->3->4->5->null
After rearranging LinkedList is as follows
1->5->2->4->3->null

Note:

We can create our own linked list in createLL() method.

So for

(1).   Input: 1->2->3->4->null

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

(2).   Input: 1->null

        Output: 1->null

(3).   Input: 1->2->null

        Output: 1->2->null

Thanks.