Reverse a Singly LinkedList without creating new LinkedList

Question

I am learning about LinkedList and tried reversing the same using Singly LinkedList collection. The challenge is list.Next is read only. So you can’t change pointers, you have to swap the value.

Also, I am to trying to attain this in the same Singly LinkedList (without creating any new LinkedList) This is my code using another LinkedList, not from Collections, but by creating Node class. Please help!

using System;
using System.Collections.Generic;
using System.Text;

namespace MyProject
{
    public class Node
    {
        public int value;
        public Node next;
        public Node(int value)
        {
            this.value = value;
            next = null;
        }
    }
    class ReverseSinglyLinkedList : Node
    {

        ReverseSinglyLinkedList(LinkedList<int> list) : base(list.First.Value)
        {
        }

        public Node reverseList(LinkedList<int> list)
        {
            LinkedListNode<int> currentNode;
            Node new_node = new Node(list.First.Value);
            currentNode = list.First.Next;
            while (currentNode != null)
            {
                Node new_currentNode = new Node(currentNode.Value);
                new_currentNode.next = new_node;
                new_node = new_currentNode;
                currentNode = currentNode.Next;
            }
            return new_node;
        }

        public static void Main(String[] args)
        {
            LinkedList<int> list = new LinkedList<int>();
            list.AddLast(1);
            list.AddLast(2);
            list.AddLast(3);
            list.AddLast(4);
            list.AddLast(5);
            ReverseSinglyLinkedList obj = new ReverseSinglyLinkedList(list);
            Node revList = obj.reverseList(list);
            while (revList != null)
            {
                Console.WriteLine(revList.value);
                revList = revList.next;
            }

        }
    }
}

So, did my answer help you find a solution? By my tests, it reverses any singly linked list on O(N) time — Flydog57, Jul 17 '20 at 03:23
So, did my answer help you with what you wanted? Is there something I can do to make it better — Flydog57, Nov 16 '21 at 02:35

Flydog57 · Answer 1 · 2020-07-12T20:33:02.287

Here's a different take on it. It walks the list, grabbing the first element and inserting it before a marker at the end. This works for N-1 elements, so there is a little fudge work at the end to handle the very last element. I'm doing this with a list of strings (rather than ints) only because it makes writing out the results easier. I tested it with ints as well.

Here's the algorithm:

private static LinkedList<T> ReverseList<T>(LinkedList<T> theList)
{
    var len = theList.Count;
    var marker = theList.Last;
    //the loop reverses all but the last element
    for (var i = 0; i < len - 1; ++i)
    {
        var currentFirst = theList.First;
        theList.RemoveFirst();
        theList.AddBefore(marker, currentFirst);
        marker = currentFirst;
    }

    //now take the last element and insert it at the beginning
    var last = theList.Last;
    theList.RemoveLast();
    theList.AddFirst(last);

    return theList;
}

Here's my call to it (using a list of string - you can try it with any type):

public static void TestReverse()
{
    var theList = new LinkedList<string>();
    theList.AddLast("1");
    theList.AddLast("2");
    theList.AddLast("3");
    theList.AddLast("4");
    theList.AddLast("5");

    var results = ReverseList(theList);

    Debug.WriteLine(string.Join(", ", theList));
}

and here's the result:

 5, 4, 3, 2, 1

It's worth noting that all those operations (Count, Last, First, RemoveFirst, AddBefore, RemoveLast and AddFirst) should be O(1) on a properly implemented singly linked list. The result is that this algorithm is O(N).

Reverse a Singly LinkedList without creating new LinkedList

1 Answers1

Linked