CODEWITHSUNDEEP
javalinked-list
h4ckerlinguist
h4ckerlinguist

Reputation: 93

How to reverse a LinkedList from a certain index, given the code fragments below

I would like to write a method public void reverseFrom(int index) which reverses a list from the given index.

I would like to only use the LinkedList class below.

public class LinkedList {

    public Node head = null;

    public class Node {
        public int value;
        public Node next;

        Node(int value, Node next) {
            this.value = value
            this.next = next;
        }
    }
}

I have a method to reverse a LinkedList:

public void reverse() {
    Node tmp = head;
    Node prev = null;
    Node nextNode = null;

    while(tmp != null) {
        nextNode = tmp.next;
        tmp.next = prev;
        prev = tmp;
        tmp = nextNode;
    }
    head = prev;
}

So far, for the reverseFrom method, I have:

public void reverseFrom(int index) {
    if(index == 0) {
        reverse();
    } else if (index == 1) {
        return;
    } else {
        Node tmp = head;
        for(int i = 0; i < index; i++) {
            tmp = tmp.next;
        }
        Node newHead = tmp;
        /*** Node prev = null;
        Node nextNode = null;
        while(newHead != null) {
            nextNode = newHead.next;
            newHead.next = prev;
            prev = newHead;
            newHead = nextNode;
        }
        newHead = prev; ***/
    }
}

I have tried using the code from reverse() but it does not work (that which is commented out). How can I then reverse the list from newHead?

Upvotes: 0

Views: 357

Answers (3)

gaydara27
gaydara27

Reputation: 70

    public void reverseFrom(int index) {
        if (index == 0) {
            reverse();

            return;
        }

        Node tmp = head;
        Node previous = null;
        for (int i = 0; i < index; i++) {
            previous = tmp;
            tmp = tmp.next;
        }
        Node newHead = tmp;

        LinkedList subLinkedList = new LinkedList();
        subLinkedList.head = newHead;
        subLinkedList.reverse();

        previous.next = subLinkedList.head;
    }

Upvotes: 1

trincot
trincot

Reputation: 350137

You could base the logic on the reverse method, but use an extra reference to the node that is at index - 1. During the loop decrement index. As long as it is positive, don't change the next reference of the current node. When it hits zero, take note of where we start the reversal, and as the current node will become the very last one, set its next reference to null. When index is negative, perform the usual reversal logic.

After the loop, check whether we need to change the head or whether we need to attach the reversed part to the node at index-1:

public void reverseFrom(int index) {
    Node tmp = head;
    Node prev = null;
    Node nextNode = null;
    Node tail = null; // node at index - 1

    while (tmp != null) {
        nextNode = tmp.next;
        if (index == 0) {
            // We arrived at the part that needs reversal
            tmp.next = null;
            tail = prev;
        } else if (index < 0) {
            // Perform normal reversal logic
            tmp.next = prev;
        }
        index--;
        prev = tmp;
        tmp = nextNode;
    }
    if (tail == null) {
        head = prev;
    } else {
        tail.next = prev;
    }
}

Upvotes: 1

Ryan
Ryan

Reputation: 1760

public class ReverseList<T> extends LinkedList<T>{
    public void reverseFrom(int idx) {
        if (idx < 0 || idx > size()) {
            return;
        }
        
        Stack<T> stack = new Stack<T>();
        while (idx < size()) {
            stack.push(remove(idx));
        }
        
        while (!stack.isEmpty()) {
            add(stack.pop());
        }
    }
    /******* Alternative slution ***************/
 public void reverseFrom(int idx) {
    if (idx < 0 || idx > size()) {
        return;
    }
    
    reverseFromInternal(idx, size()-1);
}

private void reverseFromInternal(int a, int b) {
    if (a >= b) {
        return;
    }
    T far = remove(b);
    T near = remove(a);
    
    add(a, far);
    add(b, near);
    
    reverseFromInternal(a + 1, b - 1);
}
 /****************************************/
    public static void main(String [] args) {
        ReverseList<String> list = new ReverseList<>();
        
        for (int i = 0; i < 10; i++) {
            list.add(Integer.toString(i));
        }
        list.reverseFrom(5);
        System.out.println(list);
    }
}

Upvotes: 1

Related Questions