Fading Coder

One Final Commit for the Last Sprint

Home > Tech > Content

Reversing a Subsection of a Singly Linked List

Tech 2

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

Related Articles

Understanding Strong and Weak References in Java

Strong References Strong reference are the most prevalent type of object referencing in Java. When an object has a strong reference pointing to it, the garbage collector will not reclaim its memory. F...

Comprehensive Guide to SSTI Explained with Payload Bypass Techniques

Introduction Server-Side Template Injection (SSTI) is a vulnerability in web applications where user input is improper handled within the template engine and executed on the server. This exploit can r...

Implement Image Upload Functionality for Django Integrated TinyMCE Editor

Django’s Admin panel is highly user-friendly, and pairing it with TinyMCE, an effective rich text editor, simplifies content management significantly. Combining the two is particular useful for bloggi...

Leave a Comment

Anonymous

◎Feel free to join the discussion and share your thoughts.