Good afternoon, this task:

Write a class that implements a single-linked list. The class must contain the methods Push (add an element to the top of the list), Pop (extract an element from the beginning of the list). It must also override the inherited Print method, which returns a string representation of the list. Write a Reverse method reversing the order of the elements in the list. Write a program using the class.

The problem is in the reverse method. How I did:

public void Reverse() { if (head == null) throw new ListUnderflow(); StringBuilder PrintList = new StringBuilder(); Node temp = head; while (temp != null) { PrintList.Append(temp.value); PrintList.Append(" "); temp = temp.next; } StringBuilder builder = new StringBuilder(); for (int i = PrintList.Length - 1; i >= 0; i--) { builder.Append(PrintList[i]); } string newName = builder.ToString(); Console.WriteLine(newName); }

but it’s not so true, as I was told that it was necessary not to display on the screen, but to create a new list, then call pop, and push there, and what method should return then? new list? like this:

 public SinglyLinkedList Reverse() { if (head == null) throw new ListUnderflow(); SinglyLinkedList l2 = new SinglyLinkedList(); l2.Push(Pop()); return l2; }

but I'm not sure about this turned here, can you tell?

  • 3
    Well, I would suggest that the list is generally not necessary to change, but only to expand the connection. ru.stackoverflow.com/questions/509477/… ... - pavel
  • interesting, thanks. In general, is it considered as a solution to the above assumption about a new list? - Lolidze
  • 2
    usually the reverse method does not create a new element. And changes the original. In some implementations, it generally does not change anything in the container itself, but simply sets a flag that it takes into account in other operations. - pavel
  • I am the author of the problem book from which this task was taken and, apparently, the teacher of the author of the question. I have a big request for him - solve problems on your own! - velikodniy
  • And yes, it's better to just rebuild the connection. The variant with the new list is less optimal, but it is much easier to program. - velikodniy

1 answer 1

Below are two simple implementations of the reverse list (without checks, optimizations, etc.) - iterative and recursive:

 public static void Reverse(ref Node head) { if (head == null) return; Node prev = null, current = head, next = null; while( current.Next != null ) { next = current.Next; current.Next = prev; prev = current; current = next; } current.Next = prev; head = current; } public static void ReverseUsingRecursion(Node head) { if (head == null) return; if (head.Next == null) { newHead = head; return; } ReverseUsingRecursion(head.Next); head.Next.Next = head; head.Next = null; }
  • TopiCaster has a question about singly linked lists, not about lists on arrays :) - PashaPash ♦
  • @PashaPash, and what can not work here in a single-linked list? Unless static superfluous. - Mirdin
  • @Mirdin code that was in response at the time of my comment could not quite work in a single-linked list. look at the revision history. - PashaPash ♦
  • My mistake. ;-) Did not look through the conditions, but I corrected myself ... Thanks for the comment @PashaPash - Alex Karalin