Перевернуть односвязный список с рекурсией и без нее

Question

Я новичок в структурах данных, и я знаю, что это очень распространенный вопрос. Но я знаю, что LinkedList в .NET является двусвязным, так как я буду писать код для односвязного списка в C #.

Может кто-нибудь написать пример кода?

Answer 1

Здесь используется рекурсия.

private void Reverse(Item item)
    {
        if (item == null || item.Next == null) //if head is null or we are at the tail
        {
            this.Head = item; //we are at the tail or empty list, set the new head to the tail
            return;
        }

        Reverse(item.Next);

        var nextItem = item.Next; //get the next item out, dealing with references don't want to override it
        item.Next = null;         //once you get the next item out, you can delete the *reference* i.e. link to it
        nextItem.Next = item;     //set the item you got out link to next item to the current item i.e. reverse it
    }

Answer 2

Использовать цикл (текущий элемент: currentNode, переменные, инициализированные вне цикла: previousNode, nextNode)

Set nextNode = currentNode.NextNode
Set currentNode.NextNode = previousNode
Set previousNode = currentNode
Set currentNode = nextNode
continue with loop

Answer 3

Здесь итеративное и рекурсивное связанное обращение в .net (C #) (обратите внимание, что связанный список поддерживает как первый, так и последний указатели, так что я могу добавить в конце или вставить в начале в O (1) - этого делать не нужно. Я просто определил поведение связанного списка, как указано выше)

public void ReverseIterative()
        {
            if(null == first)
            {
                return;
            }
            if(null == first.Next)
            {
                return;
            }
            LinkedListNode<T> p = null, f = first, n = null;
            while(f != null)
            {
                n = f.Next;
                f.Next = p;
                p = f;
                f = n;
            }
            last = first;
            first = p;
        }

Рекурсивный:

        public void ReverseRecursive()
        {
            if (null == first)
            {
                return;
            }
            if (null == first.Next)
            {
                return;
            }
            last = first;
            first = this.ReverseRecursive(first);
        }
        private LinkedListNode<T> ReverseRecursive(LinkedListNode<T> node)
        {
            Debug.Assert(node != null);
            var adjNode = node.Next;
            if (adjNode == null)
            {
                return node;
            }
            var rf = this.ReverseRecursive(adjNode);
            adjNode.Next = node;
            node.Next = null;
            return rf;
        }

Answer 4

//Have tried the Iterative approach as below, feel free to comment / optimize 

package com.test;


public class ReverseSinglyLinkedList {


public ReverseSinglyLinkedList() {
    // TODO Auto-generated constructor stub
}
public Node ReverseList(Node n)
{

    Node head =  n; 
    Node current = n; 
    Node firstNodeBeforeReverse = n;  // keep track of origional FirstNode

    while(true) 
    {

        Node temp = current; 
         // keep track of currentHead in LinkedList "n", for continued access to unprocessed List
        current = current.next; 
        temp.next = head;
          // keep track of head of Reversed List that we will return post the processing is over 
        head = temp;   

        if(current.next == null)
        {

            temp = current;
            current.next = head;
            head = temp;        
                            // Set the original FirstNode to NULL
            firstNodeBeforeReverse.next = null; 

            break;
        }
    } 

    return head;

}

public void printLinkList(Node n)
{

    while(true)
    {
        System.out.print(n.data + " ");
        n = n.next;
        if(n.next ==null)
        {
            System.out.print(n.data + " ");
            break;
        }

    }
}

public static void main(String[] args) {
    // TODO Auto-generated method stub

    // TEST THE PROGRAM: crate a node List first to reverse it
    Node n = new Node(1);
    n.next = new Node(2);
    n.next.next = new Node(3);
    n.next.next.next = new Node(4);
    n.next.next.next.next = new Node(5);
    n.next.next.next.next.next = new Node(6);

    ReverseSinglyLinkedList r = new ReverseSinglyLinkedList();
    System.out.println("Input Linked List : ");  
    r.printLinkList(n);

    Node rsList = r.ReverseList(n);

    System.out.println("\n Reversed Linked List : ");
    r.printLinkList(rsList);



}

}

Answer 5

Поскольку это, скорее всего, домашнее задание, я собираюсь заявить об этом таким образом, который может быть довольно запутанным, чтобы не выполнять всю работу. Надеюсь, моя попытка не просто запутает (что очень возможно).

Когда у вас есть ссылка на узел в списке (скажем, первый узел), у вас также есть ссылка на узел, следующий за ним. Вам просто нужно сделать так, чтобы следующий узел ссылался на ваш текущий узел, сохраняя при этом достаточно информации о следующем узле (и его предыдущем состоянии), чтобы выполнить аналогичную работу для него. Теперь единственные хитрые части имеют дело с граничными условиями (начало и конец списка).

Answer 6

reversed_list = new
for all node in the original list
   insert the node to the head of reversed_list

Answer 7

Вам необходимо определить структуру данных узла, которая содержит некоторые данные и ссылку на следующий узел в связанном списке. Что-то вроде:

class Node {
  private Node _next;
  private string _data;

  public Node(string data) {
    _next = null;
    _data = data;
  }

  // TODO: Property accessors and functions to link up the list
}

Затем вы можете написать алгоритм для циклического перебора списка в обратном порядке, создав новый перевернутый список.