Answer to Question #230854 in Java | JSP | JSF for Rishav

Question

Problem 5: Suppose there is a list s1->s2->s3->………->sn-1 ->sn. given to you. You need to modify this list in such a way that it will be s1->sn ->s2->sn-1 ->s3->sn-2……. Note: algorithm should be inplace without modifying the values of the nodes. Marking Scheme: Total 10 marks ( Algorithm explanation + Pseudo-code + runtime and data structure used)

Answer 1

Algorithm Explanation

• Start by creating an empty deque
• Put all the elements of the linked list to the created deque
• Put all the elements back to the linked list in an alternate way.

Pseudocode

package rearrangingelements;
import java.util.*;
import java.lang.*;
import java.io.*;
public class RearrangingElements {




  
    static class List
    {
        int element;
        List nextNode;
        List(int element)
        {
            this.element = element;
            nextNode = null;
        }
    }
     
    // Displaying the linked list
    static void displayList(List node)
    {
        List tempNode = node;
        while (tempNode != null)
        {
            System.out.print(tempNode.element + " ");
            tempNode = tempNode.nextNode;
        }
    }
 
    /* Function for reversing the list */
    static void arrangingList(List node )
    {
        // Creating a deque
        Deque<Integer> deque = new ArrayDeque<>();
        List tempNode = node;
         
        // Pushing all the items of the list to the deque
        while(tempNode != null)
        {
            deque.addLast(tempNode.element);
            tempNode = tempNode.nextNode;
        }
        tempNode = node;
        int i = 0;
         
        
        while(!deque.isEmpty())
        {
            if(i % 2 == 0)
            {
                tempNode.element = deque.removeFirst();
            }
            else
            {
                tempNode.element = deque.removeLast();
            }
            i++;
            tempNode = tempNode.nextNode;
        }
    }
 
    // Testing code
    public static void main (String[] args)
    {
        // Creating linked list s1->s2->s3->s4->s5
        List node = null;
         
        node = new List(1);
        node.nextNode = new List(2);
        node.nextNode.nextNode = new List(3);
        node.nextNode.nextNode.nextNode = new List(4);
        node.nextNode.nextNode.nextNode.nextNode = new List(5);
 
        System.out.println("Linked list before arrangement");
        displayList(node);
        arrangingList(node);
        System.out.println("\nAfter rearrangement");
        displayList(node);
    }
}

Time Complexity is O(n)
Data structures used ares deque and linked list