Inverser une liste unidirectionnelle avec et sans utiliser la récursivité

Question

Je suis novice dans les structures de données, et je sais que c'est une question très courante à poser. Mais je sais que LinkedList dans .NET est doublement lié, alors comment je vais écrire du code pour une liste à un seul lien en C#.

Est-ce que quelqu'un pourrait écrire un exemple de code?

Answer 1

Vous devez définir une structure de données de noeud contenant des données et une référence au noeud suivant dans la liste chaînée. Quelque chose comme:

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 
} 

Ensuite, vous pouvez écrire un algorithme à boucle sur la liste dans l'ordre inverse, la construction d'une nouvelle liste inversée.

Answer 2

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

Answer 3

boucle d'utilisation (élément courant: currentNode, les variables initialzied en dehors boucle: previousNode, nextNode)

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

Answer 4

Depuis cela devoirs probablement, je vais dire cela d'une manière qui pourrait être assez déroutant pour ne pas faire tout le travail. J'espère que ma tentative ne rendra pas les choses plus confuses (ce qui est hautement possible).

Lorsque vous avez une référence à un nœud dans la liste (disons le premier nœud), vous avez également une référence au nœud qui le suit. Vous avez juste besoin de faire référence au nœud suivant à votre nœud actuel tout en gardant suffisamment d'informations autour du nœud suivant (et de son état précédent) pour effectuer un travail similaire. Maintenant, les seules parties délicates concernent les conditions aux limites (le début et la fin de la liste).

Answer 5

Ici, il utilise la récursivité.

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 6

//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 7

est lié ici inversion itérative et récursive en .net (C#) (notez la liste chaînée est maintenant à la fois premier et dernier pointeurs afin que je puisse ajouter à la fin ou insérer à la tête dans O . (1) - on n'a pas à faire ce que je viens de définir mon comportement de liste chaînée comme ci-dessus)

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

récursive:

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