Question

Chapter 20, programming challenge 2: Linked List Sorting and Reversing

Modify the LinkedList1 class presented in this chapter by adding sort() and reverse() methods. The reverse method reverses the order of the elements in the list, and the sort method rearranges the elements in the list so they are sorted in alphabetical order. Do not use recursion to implement either of these operations. Extend the graphical interface in the LinkedListDemo class to support sort and reverse commands, and use it to test the new methods.

This must be done in java (netbeans)

Answer 1

Dear Student,

Please find the code for linked list reverse:

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    /* Function to reverse the linked list */

    Node reverse(Node node)

    {

        Node prev = null;

        Node current = node;

        Node next = null;

        while (current != null) {

            next = current.next;

            current.next = prev;

            prev = current;

            current = next;

        }

        node = prev;

        return node;

    }

  

    // prints content of double linked list

    void printList(Node node)

    {

        while (node != null) {

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

            node = node.next;

        }

    }

  

    public static void main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(85);

        list.head.next = new Node(15);

        list.head.next.next = new Node(4);

        list.head.next.next.next = new Node(20);

  

        System.out.println("Given Linked list");

        list.printList(head);

        head = list.reverse(head);

        System.out.println("");

        System.out.println("Reversed linked list ");

        list.printList(head);

    }

}

Please find the code for linked list sorting :

public class SortList {
  
//Represent a node of the singly linked list
class Node{
int data;
Node next;
  
public Node(int data) {
this.data = data;
this.next = null;
}
}

//Represent the head and tail of the singly linked list
public Node head = null;
public Node tail = null;
  
//addNode() will add a new node to the list
public void addNode(int data) {
//Create a new node
Node newNode = new Node(data);
  
//Checks if the list is empty
if(head == null) {
//If list is empty, both head and tail will point to new node
head = newNode;
tail = newNode;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail.next = newNode;
//newNode will become new tail of the list
tail = newNode;
}
}
  
//sortList() will sort nodes of the list in ascending order
public void sortList() {
//Node current will point to head
Node current = head, index = null;
int temp;
  
if(head == null) {
return;
}
else {
while(current != null) {
//Node index will point to node next to current
index = current.next;
  
while(index != null) {
//If current node's data is greater than index's node data, swap the data between them
if(current.data > index.data) {
temp = current.data;
current.data = index.data;
index.data = temp;
}
index = index.next;
}
current = current.next;
}
}
}
  
//display() will display all the nodes present in the list
public void display() {
//Node current will point to head
Node current = head;
if(head == null) {
System.out.println("List is empty");
return;
}
while(current != null) {
//Prints each node by incrementing pointer
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
  
public static void main(String[] args) {
  
SortList sList = new SortList();
  
//Adds data to the list
sList.addNode(9);
sList.addNode(7);
sList.addNode(2);
sList.addNode(5);
sList.addNode(4);
  
//Displaying original list
System.out.println("Original list: ");
sList.display();
  
//Sorting list
sList.sortList();
  
//Displaying sorted list
System.out.println("Sorted list: ");
sList.display();
}
}

Happy Learning