Reverse Linked List Between a range

amitsen01ei

Aug 27th, 2023

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

Java 5.14 KB | Source Code | 0 0

raw download clone embed print report

import java.util.*;
import java.util.stream.*;
class Node<E> {
E element;
Node<E> next;
Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
Node(E element) {
this.element = element;
this.next = null;
}
@Override
public String toString() {
return String.format("{ element : %s }",
(element == null ? "null" : element.toString()));
}
}
class MyLinkedList<E> implements Iterable<E> {
Node<E> head;
Node<E> tail;
int size;
MyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
void addLast(E value) {
final var newNode = new Node<>(value, null);
if (this.head == null) {
this.head = newNode;
} else {
this.tail.next = newNode;
}
this.tail = newNode;
++this.size;
}
/**
* Adds the iterable support for using this custom linked list in an enhanced for loop.
* @return the Iterable object of this custom linked list.
*/
@Override
public Iterator<E> iterator() {
return new Iterator<>() {
Node<E> current = head;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public E next() {
E value = current.element;
current = current.next;
return value;
}
};
}
/**
* Adds Stream API support on this custom implementation of the generic linked list
* @return the stream object of the custom linked list
*/
Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
/**
* Prints a linked list in a formatted fashion given its head node. This function relies on
* the custom implementation of a generic linked list above.
* @param head the head node of a linked list
* @param <E> denotes the generic type
*/
static <E> void print(Node<E> head) {
var sb = new StringBuilder("[");
Node<E> current = head;
if (current != null) {
sb.append(current.element);
current = current.next;
}
while (current != null) {
sb.append(",").append(current.element);
current = current.next;
}
sb.append("]");
System.out.println(sb);
}
}
public class ReverseInRange {
/**
* REQUIRES MINIMUM JDK 10 or above
*
*
* This function reverses a linked list for a given range. The range is assumed to be
* 1-based, unlike 0-based indexing like array. The function relies on the custom
* implementation of a generic linked list above.
*
*
* Time complexity: In the worst case where we need to reverse the entire list,
* the time complexity of this function would be O(N) where N denotes the size of the list
*
*
* Space complexity: In the worst case, the function uses constant memory. So the space complexity
* would be O(1)
*
* @param head the head node of the linked list
* @param left an integer denoting starting position (inclusive)
* @param right and integer denoting ending position (inclusive)
* @return the updated head of the reversed linked list
* @param <E> denotes the generic type
*/
private static <E> Node<E> reverseInRange(Node<E> head, int left, int right) {
if (left < 1 || right < 1 || left > right) {
throw new IllegalArgumentException("Invalid range values");
}
if (head == null || left == right) {
return head;
}
var temp = new Node<E>(null);
temp.next = head;
Node<E> prev = temp;
for (var i = 0; i < left - 1; i++) {
prev = prev.next;
}
Node<E> start = prev.next;
Node<E> then = start.next;
for (var i = 0; i < right - left; i++) {
start.next = then.next;
then.next = prev.next;
prev.next = then;
then = start.next;
}
head = temp.next;
return head;
}
public static void main(String[] args) {
try (var sc = new Scanner(System.in)) {
int n = sc.nextInt();
var linkedList = new MyLinkedList<Integer>();
for (var i = 0; i < n; i++) {
linkedList.addLast(sc.nextInt());
}
int left = sc.nextInt();
int right = sc.nextInt();
System.out.println("Original List: " + linkedList.stream()
.map(Objects::toString)
.collect(Collectors.joining(",", "[", "]")));
var head = reverseInRange(linkedList.head, left, right);
System.out.printf("Reversed (From %d To %d): ", left, right);
MyLinkedList.print(head);
}
}
}

Add Comment

Please, Sign In to add comment