Инвертировать одиночный связанный список без создания нового списка - PullRequest
Новая
       48

Инвертировать одиночный связанный список без создания нового списка

1 голос
/ 12 июля 2020

Я изучаю LinkedList и пробовал изменить то же самое, используя коллекцию Singly LinkedList. Задача - список. Далее идет только для чтения . Таким образом, вы не можете менять указатели, вам нужно поменять местами значение. не из Коллекций, а путем создания класса Node. Пожалуйста, помогите! 

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;
            }

        }
    }
}

1 Ответ

0 голосов
/ 12 июля 2020

Вот другой взгляд на это. Он проходит по списку, берет первый элемент и вставляет его перед маркером в конце. Это работает для элементов N-1, поэтому в конце нужно немного поработать, чтобы обработать самый последний элемент. Я делаю это со списком строк (а не целых чисел) только потому, что это упрощает запись результатов. Я также тестировал его с помощью int.

Вот алгоритм: 

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;
}

Вот мой призыв к нему (используя список string - вы можете попробовать его с любым типом): 

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));
}

и вот результат: 

 5, 4, 3, 2, 1

Стоит отметить, что все эти операции (Count, Last, First, RemoveFirst, AddBefore , RemoveLast и AddFirst) должны быть O (1) в правильно реализованном односвязном списке. В результате этот алгоритм O (N).

...