Question

public class LinkedList {
  
  
   // The LinkedList Node class
   private class Node{
      
       int data;
       Node next;
      
       Node(int gdata)
       {
           this.data = gdata;
           this.next = null;
       }
      
   }
  
   // The LinkedList fields
   Node head;
  
   // Constructor
   LinkedList(int gdata)
   {
       this.head = new Node(gdata);
   }
  
   public void Insertend(int gdata)
   {
       Node current = this.head;

       while(current.next!= null)
       {
           current = current.next;
       }
      
       Node newnode = new Node(gdata);
       current.next = newnode;
      
   }
  
   public void Listprint()
   {
       Node current = this.head;

       while(current!= null)
       {
           System.out.print(current.data + " ");
           current = current.next;
       }
      
       System.out.println();
      
   }
  
  
  
   public void Listsort(Node start)
   {
   // Complete this method to sort a Linked list
   // Return the first node in the sorted list
   // Feel free to change the method type, add/remove parameters
   // Full credit (30 points) will be awarded for an algorithm that is O(nlog n).
   // Algorithms that are O(n^2) slower will be scored out of 10 points.
  
  
  
      
   }
  
   public static void main(String[] args) {
      
       LinkedList exlist = new LinkedList(0);
       exlist.Insertend(1);
       exlist.Insertend(5);
       exlist.Insertend(2);
       exlist.Insertend(7);
       exlist.Insertend(10);
       exlist.Insertend(3);
      
       exlist.Listprint();
       //output: 0 1 5 2 7 10 3
       exlist.Listsort(exlist.head);
       exlist.Listprint();
       //output should be: 0 1 2 3 5 7 10
      
      
   }
  
  
  

}

Implement Problem 1 in Java.

Note:

Find a file called LinkedList.java in assignment 6 folder.

Complete the method of Listsort().

Test your method in the main method provided following the comments.

Answer 1

CODE:

public class LinkedList {

    // The LinkedList Node class

    private class Node {

        int data;

        Node next;

        Node(int gdata) {

            this.data = gdata;

            this.next = null;

        }

    }

    // The LinkedList fields

    Node head;

    // Constructor

    LinkedList(int gdata) {

        this.head = new Node(gdata);

    }

    public void Insertend(int gdata) {

        Node current = this.head;

        while (current.next != null) {

            current = current.next;

        }

        Node newnode = new Node(gdata);

        current.next = newnode;

    }

    public void Listprint() {

        Node current = this.head;

        while (current != null) {

            System.out.print(current.data + " ");

            current = current.next;

        }

        System.out.println();

    }

    public Node merge(Node l, Node r) {

        Node tmp = null;

        // if left node is null return right as null l denotes left linked list is empty

        if (l == null)

            return r;

        if (r == null)

            return l;

        // merge the linked by comparing each value

        // like we merge two sorted arrays

        if (l.data <= r.data) {

            tmp = l;

            tmp.next = merge(l.next, r);

        } else {

            tmp = r;

            tmp.next = merge(l, r.next);

        }

        return tmp;

    }

    // using recurive approch merge sort

    public Node Listsort(Node start) {

        // if linked list has only one or no nodes

        if (start == null || start.next == null) {

            return start;

        }

        // find the middle like we generally do in merge sort for arrays

        Node middle = findMiddle(start);

        // temporarly storing next of middle middle node

        Node middleNext = middle.next;

        // and making next of middle to null to divide the linked list

        middle.next = null;

        // Recursively diving linked it

        // first part

        Node l = Listsort(start);

        // second part

        Node r = Listsort(middleNext);

        // merge the linked

        Node after_sorting = merge(l, r);

        return after_sorting;

    }

    // using fast and slow pointer concept to find middle of the linked in O(n/2)

    // time complexity

    // when the fast pointer reaches the end Node the slow pointer is at the middle

    public static Node findMiddle(Node head) {

        if (head == null)

            return head;

        Node slow = head, fast = head;

        while (fast.next != null && fast.next.next != null) {

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

    public static void main(String[] args) {

        LinkedList exlist = new LinkedList(0);

        exlist.Insertend(1);

        exlist.Insertend(5);

        exlist.Insertend(2);

        exlist.Insertend(7);

        exlist.Insertend(10);

        exlist.Insertend(3);

        exlist.Listprint();

        // output: 0 1 5 2 7 10 3

        exlist.Listsort(exlist.head);

        exlist.Listprint();

        // output should be: 0 1 2 3 5 7 10

    }

}

OUTPUT:

Please upvote if you like my answer and comment below if you have any queries.