How can I inverse a list of elements if I can only access to an element and his next one?

Question

I have been given a "class" called LinkedList which has only one atributte "Node first" which refers to the first element of a list. The way to access the other ones is that class "Node" has access to an element 'x' and his following one:

public class LinkedList<T> {
    private static class Node<E> {
        E elem;
        Node<E> next;

        Node (E elem) {
            this.elem = elem;
            this.next = null;
        }
    }

    private Node<T> first;

So that, I have been ordered to do a method called "reverse" from class "LinkedList" which has to reverse the list. However, the difficulty of the exercise is that I can only re-link the attributte "first", I mean I cannot create auxiliar data structures and that type of help.

I have done this in order to achieve the last element of the list, but I dont know how to continue:

    public void reverse () {
        Node<T> aux = first.next;
        while (aux.next != null) {
            first.elem = aux.elem;
            aux = aux.next;
        }
        first.elem = aux.elem;
    }

Marja van der Wind · Accepted Answer · 2023-01-18 12:32:36Z

1

It seems quite a theoretical question to me, so you might want to check Geek for Geeks first. Most of these questions that are used in programming courses are well explained there, including coding examples.

In this case, a well-known solution is to use three pointers: a current number, the previous number , and the next number; to keep track of nodes to update reverse links. Check here: https://www.geeksforgeeks.org/reverse-a-linked-list/

answered Jan 18, 2023 at 12:32

Marja van der Wind

3301 silver badge14 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Carlos Pinzón · Accepted Answer · 2023-07-17 13:42:20Z

One solution is to think recursively. In order to reverse the list, it suffices to isolate the first node, recursively reverse the list from the second element to the end, and append the first node at the very end. This means that your reverse function will need to receive not just the first node of the list to be reversed, but also, optionally, a node to be appended at the end.

Since your function must now not just reverse but also append an element to the end, you can isolate the first node, append the extra nodes to it, and then call your function to reverse from the second to the end, appending the first node to the result.

You can test the following js implementation in your browser console:

function reverse(h, append=null){
  let next = h.next;
  h.next = append;
  if(!next) return h;
  return reverse(next, h);
}

reverse({value:1, next:{value:2, next:{value:3, next:{value:4, next:null}}}})
// yields:
{ value: 4, next: { value: 3, next: { value: 2, next: { value: 1, next: null } } } }

Collectives™ on Stack Overflow

How can I inverse a list of elements if I can only access to an element and his next one?

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related