Reversing a Subsection of a Singly Linked List
A singly linked list consists of nodes, each containing a data element and a reference too the next node.
import java.util.Scanner;
public class LinkedList<E> {
private int count = 0;
private class ListNode {
E value;
ListNode successor;
ListNode(E value, ListNode successor) {
this.value = value;
this.successor = successor;
}
}
}
To insert nodes, the first node becomes the head, and subsqeuent nodes are appended at the end.
public ListNode insert(E element) {
ListNode head = null;
Scanner input = new Scanner(System.in);
while (true) {
System.out.println("Enter data or 'exit' to quit:");
String entry = input.next();
if (entry.equals("exit")) {
break;
}
if (head == null) {
head = new ListNode((E) entry, null);
} else {
ListNode current = head;
while (current.successor != null) {
current = current.successor;
}
current.successor = new ListNode((E) entry, null);
}
count++;
}
return head;
}
Traversing the list starts from the head node.
public void traverse(ListNode head) {
ListNode current = head;
if (head == null) {
System.out.println("List is empty");
return;
}
while (current != null) {
System.out.print(current.value + " ");
current = current.successor;
}
System.out.println();
}
Reverisng a specified range involves storing node values in an array, reversign the array, and reassigning them.
public ListNode reverseRange(ListNode head, int start, int end) {
if (head == null || start < 1 || start > count || end < 1 || end > count || start >= end) {
return head;
}
ListNode previous = null;
ListNode startNode = head;
E[] values = (E[]) new Object[end - start + 1];
for (int i = 1; i <= end; i++) {
if (i == start - 1) {
previous = startNode;
}
if (i >= start && i <= end) {
values[i - start] = startNode.value;
}
startNode = startNode.successor;
}
ListNode endNode = startNode;
for (int i = 0; i < values.length / 2; i++) {
E swap = values[i];
values[i] = values[values.length - i - 1];
values[values.length - i - 1] = swap;
}
ListNode temp = previous;
for (int i = 0; i < values.length; i++) {
temp.successor.value = values[i];
temp = temp.successor;
}
return head;
}
Testing the implementation:
LinkedList<String> list = new LinkedList<>();
LinkedList<String>.ListNode head = list.insert("aa");
list.traverse(head);
list.reverseRange(head, 2, 4);
System.out.println("List after reversal:");
list.traverse(head);
Original list: aa bb cc dd ee ff gg Reversed list: aa dd cc bb ee ff gg