Question

Suppose there is a list s1->s2->s3->.........->sn-1

->sn. given to you. Write the algorithm and the pseudo code to modify this list in

such a way that it will be s1->sn

->s2->sn-1

->s3->sn-2.......

Note: algorithm should be in place 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 
-Make an empty deque
- Place all the items of the linked list to the deque created.
- Put all the items back to the linked list in alternate manner from the deque.






Java Code or the Pseudocode



package linkedlistarrangement1;








// A java program for rearranging element in a linked list
import java.util.*;
import java.lang.*;
import java.io.*;
 
public class LinkedListArrangement1 
{
    
    static class ListNode
    {
        int element;
        ListNode nextNode;
        ListNode(int element)
        {
            this.element = element;
            nextNode = null;
        }
    }
     
    
    static void displayList(ListNode node)
    {
        ListNode tempNode = node;
        while (tempNode != null)
        {
            System.out.print(tempNode.element + " ");
            tempNode = tempNode.nextNode;
        }
    }
 
    /* Function for reversing the given linked list  */
    static void rearranging(ListNode node)
    {
        
        Deque<Integer> queue = new ArrayDeque<>();
        ListNode tempNode = node;
         
       
        while(tempNode != null)
        {
            queue.addLast(tempNode.element);
            tempNode = tempNode.nextNode;
        }
        tempNode = node;
        int i = 0;
         
        
        while(!queue.isEmpty())
        {
            if(i % 2 == 0)
            {
                tempNode.element = queue.removeFirst();
            }
            else
            {
                tempNode.element= queue.removeLast();
            }
            i++;
            tempNode = tempNode.nextNode;
        }
    }
 
    // Testing  code
    public static void main (String[] args)
    {
        // Creating a list such as  1->2->3->4->5
        ListNode node = null;
         
        node = new ListNode(1);
        node.nextNode = new ListNode(2);
        node.nextNode.nextNode = new ListNode(3);
        node.nextNode.nextNode.nextNode = new ListNode(4);
        node.nextNode.nextNode.nextNode.nextNode = new ListNode(5);
 
        System.out.println("Before rearrangement the linked list is:");
        displayList(node);
        rearranging(node);
        System.out.println("\nAfter the rearrangement the linked list becomes");
        displayList(node);
    }
}
 

Time Complexity for the above algorithm is O(n)
Data structure used in the algorithm is deque