Question

JAVA Program: reverse a linked list and find the middle node in the linked list.

inFile (use argv[1]): A text file contains a list of English words (strings), giving below

outFile1 (use argv[2])a text file includes

      i) The completed sorted linked list, in ascending order.

//With caption indicating you are printing the original sorted list

      ii) The reversed linked list.

//With caption indicating you are printing the reversed sorted list

      outFile2( use argv[3]): All debugging outputs.

                        (Do not print this file in the hard copy!! )

string list in a text file:

Hishaam Esteban Kevin

Matthew    Brandon

Joel Luis     Jianwei Yechiel

Taeyong

Jiayu

Jiade Phillip

Russell         Mohebullah

Akshar   Evgeniia       Andres   Marco Justin

Robin Kelvin Zhiheng Jeffrey

Yifei Yinyu

Jiaxin Youyia Eleftherios

Yuan

  Must have all the object classes as given below.

********************************

- listNode class

- data (string)

- next (listNode *)

methods:

- printNode (node) // use the format:

(this node’ data, this node’s memo address, next node’s memo address, next node’s data)

see print list example below.

- A linkedList class

- listHead (listNode *) // Initially it points to a dummy node

methods:

- constructLL (…)

- findMiddleNode (…) // This method is not called in this project!

- reverseLL(…) // See algorithm steps below.

- moveSpotNodeToFront (listHead, Spot) // on your own!

            // this method moves the node which is pointed by Spot to the front of the list.

// i.e., listHead’s next is pointing to the node in the front of the list.

- listInsert (…)

- findSpot (…) // Use the findSpot algorithm steps taught in class.

- printList (listHead, outFile)

// print the list to outFile, from listHead to the end of the list in the following format:

listHead -> (this node’ data, this node’s memo address, next node’s memo address, next node’s data) -> (this node’ data, this node’s memo address, next node’s memo address, next node’s data) -> . . . . . -> NULL

Answer 1

Answer:

Given that:

class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
  
Node reverseUtil(Node curr, Node prev)
{
if (curr.next == null) {
head = curr;
curr.next = prev;
return head;
}
  
Node next1 = curr.next;
curr.next = prev;
reverseUtil(next1, curr);
return head;
}

void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
}

Find Middle

void printMiddle()
{
Node slow_ptr = head;
Node fast_ptr = head;
if (head != null)
{
while (fast_ptr != null && fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
System.out.println("The middle element is [" + slow_ptr.data + "] \n");
}
}

Sort linked 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;
}
}
}