Question

Please do this in Java!!!

Describe a method for performing a card shuffle of a singly linked list of 2n elements, by
converting it into two lists. A card shuffle is a permutation where a list L is cut
into two lists, L1 and L2, where L1 is the first half of L and L2 is the second half
of L, and then these two lists are merged into one by taking the first element in
L1, then the first element in L2, followed by the second element in L1, the second
element in L2, and so on.
Assume the input list is a singly linked list. Your algorithm has to perform the shuffle
in-place, i.e., it is allowed to use only O(1) additional memory cells. So, you are not allowed
to use any additional (or duplicate) list of any kind that may use more than O(1) cells.

Answer 1

Space complexity: O(1).

Note: example is just shown for explanation purpose only.

Required 'shuffle' method(java):   

public static LinkedList shuffle(LinkedList card)
    {//divide list into two equal list.

    // example: list :1->2->3->4->5->6->7->8.
     //List L1: 1->2->3->4->null.         List L2:5->6->7->8->null.

      //List L1 head.
       Node L1_head=card.head;
     
       //List L2_head
       Node L2_head=findMiddleNode(card);
       
      //Current pointer to traverse the list L1.
      Node L1_currNode=L1_head;
      //next pointer of current pointer of List L1.
      Node L1_nextptr=L1_currNode.next;
    
      //Current pointer to traverse the list L2.
      Node L2_currNode=L2_head;
      //next pointer of current pointer of List L2.
      Node L2_nextptr=L2_currNode.next;
    
      while(L2_nextptr!=null)
      {
        //exchange the link between List L1 and L2.
        L1_currNode.next=L2_currNode;
        L2_currNode.next=L1_nextptr;
    
        //Incrementing the list L1 pointers.
        L1_currNode=L1_nextptr;
        L1_nextptr=L1_nextptr.next;
      
        //Incrementing the list L2 pointers.
        L2_currNode=L2_nextptr;
        L2_nextptr=L2_nextptr.next;
     
      }
       //exchange the last node links of List L1 and L2.
       L1_currNode.next=L2_currNode;
       L2_currNode.next=null;
    
       //retrun the reference of head.
      return card;
    }

   Complete java code:

   
public class LinkedList {

    Node head; // head of list
    static class Node {

        int data;
        Node next;

      
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    //insert data into linked List.
    public static LinkedList insert(LinkedList card, int data)
    {
    
        Node new_node = new Node(data);
        new_node.next = null;

      
        if (card.head == null) {
            card.head = new_node;
        }
        else {
          
            Node last = card.head;
            while (last.next != null) {
                last = last.next;
            }

            last.next = new_node;
        }

     
        return card;
    }
    public static Node findMiddleNode(LinkedList card)
    {
      Node slowPointer=card.head;
      Node fastPointer=card.head;
    
      while(fastPointer!=null)
      {
         slowPointer=slowPointer.next;
         fastPointer=fastPointer.next.next;
      }
    
      return slowPointer;
    }
  
    public static LinkedList shuffle(LinkedList card)
    {//divide list into two equal list.
     
      //List L1 head.
       Node L1_head=card.head;
     
       //List L2_head
       Node L2_head=findMiddleNode(card);
       
      //Current pointer to traverse the list L1.
      Node L1_currNode=L1_head;
      //next pointer of current pointer of List L1.
      Node L1_nextptr=L1_currNode.next;
    
      //Current pointer to traverse the list L2.
      Node L2_currNode=L2_head;
      //next pointer of current pointer of List L2.
      Node L2_nextptr=L2_currNode.next;
    
      while(L2_nextptr!=null)
      {
        //exchange the link between List L1 and L2.
        L1_currNode.next=L2_currNode;
        L2_currNode.next=L1_nextptr;
    
        //Incrementing the list L1 pointers.
        L1_currNode=L1_nextptr;
        L1_nextptr=L1_nextptr.next;
      
        //Incrementing the list L2 pointers.
        L2_currNode=L2_nextptr;
        L2_nextptr=L2_nextptr.next;
     
      }
       //exchange the last node links of List L1 and L2.
       L1_currNode.next=L2_currNode;
       L2_currNode.next=null;
    
       //retrun the reference of head.
      return card;
    }
    public static void printList(LinkedList card)
    {
        Node currNode = card.head;

        System.out.print("Card: ");

        while (currNode != null) {
            System.out.print(currNode.data + " ");

          
            currNode = currNode.next;
        }
    }

  
    public static void main(String[] args)
    {
        /* Start with the empty list. */
        LinkedList card = new LinkedList();
      
        //insert the data into LinkedList.
        card=insert(card,1);
        card=insert(card,2);
        card=insert(card,3);
        card=insert(card,4);
        card=insert(card,5);
        card=insert(card,6);
        card=insert(card,7);
        card=insert(card,8);
      
        printList(card);
      
        card=shuffle(card);
        System.out.println("\n\nAfter shulfle: ");
        printList(card);
      
     
    }
}

Output:

Card: 1 2 3 4 5 6 7 8 Node slowPointer=card.head; Node fastPointer=card.head; After shulfle: Card: 1 5 2 6 3 7 4 8 while(fastPointer !=null) slowPointerEslowPointer.next; fastPointer-fastPointer.next.next; return slowPointer; public static LinkedList shuffle(Linkedlist card), {//divide list into two equal list. //List Li head. Node Li_head=card.head; //List L2_head Node L2_head=findMiddleNode(card); //Current pointer to traverse the list L1. Node L1_currNode=L1_head; //next pointer of current pointer of List L1. Node L1_nextptr=L1_currNode.next; //Current pointer to traverse the list L2.