在递归函数中颠倒链表c＃

Question

我在尝试为我在C＃中创建的LinkedList类编写反向递归方法时出现问题。 该链表中有两个指针之一的头，另一个用于尾部：

public class Node 
{ 
    public object data; 
    public Node next; 
    public Node(object Data) 
    { 
     this.data = Data; 
    } 
} 

public class LinkedList 
{ 
    Node head; 
    Node tail; 
    public void Add(Node n) 
    { 
     if (head == null) 
     { 
      head = n; 
      tail = head; 
     } 
     else 
     { 
      tail.next = n; 
      tail = tail.next; 
     } 
    } 

现在，递归反向功能是这样的：

public void reverse_recursive() 
    { 
     Node temp_head = head; 
     if (temp_head == tail) 
     { 

      return; 
     } 

     while (temp_head != null) 
     { 
      if (temp_head.next == tail) 
      { 
       tail.next = temp_head; 
       tail = temp_head; 
       reverse_recursive(); 
      } 
      temp_head = temp_head.next; 
     } 
    } 

我有2个与烦恼它：首先是一个逻辑问题，我知道这个头在逆向后并不指向第一个节点。第二个问题是我可能对空指针做错了，所以程序崩溃了。

我也给你的主要程序：

class Program 
{ 
    static void Main(string[] args) 
    { 
     LinkedList L = new LinkedList(); 
     L.Add(new Node("first")); 
     L.Add(new Node("second")); 
     L.Add(new Node("third")); 
     L.Add(new Node("forth")); 
     L.PrintNodes(); 
     L.reverse_recursive(); 
     L.PrintNodes(); 
     Console.ReadLine(); 
    } 
} 

谢谢你的帮助！

Answer 1

 public void reverse() 
     { 
      reverse_recursive(tail); 

      Node tmp = tail; 
      tail = head; 
      head = tmp; 
     } 

     public void reverse_recursive(Node endNode) 
     { 
      Node temp_head = head; 
      if (temp_head == endNode) 
      { 
       return; 
      } 

      while (temp_head != null) 
      { 
       if (temp_head.next == endNode) 
       { 
        break; 
       } 
       temp_head = temp_head.next; 
      } 

      endNode.next = temp_head; 
      temp_head.next = null; 
      reverse_recursive(temp_head); 
     } 

也this

Answer 2

public void Reverse() 
{ 
    this.Reverse(this.head); 
} 

private void Reverse(Node node) 
{ 
    if (node != null && node.next != null) 
    { 
     // Create temporary references to the nodes, 
     // because we will be overwriting the lists references. 
     Node next = node.next; 
     Node afterNext = node.next.next; 
     Node currentHead = this.head; 

     // Set the head to whatever node is next from the current node. 
     this.head = next; 

     // Reset the next node for the new head to be the previous head. 
     this.head.next = currentHead; 

     // Set the current nodes next node to be the previous next nodes next node :) 
     node.next = afterNext; 

     // Keep on trucking. 
     this.Reverse(node); 
    } 
    else 
    { 
     this.tail = node; 
    } 
} 

Answer 3

另一种选择，请参阅在这里。

class Program{ 
    static void Main(string[] args) 
    { 
     LinkedList L = new LinkedList(); 
     L.Add(new Node("first")); 
     L.Add(new Node("second")); 
     L.Add(new Node("third")); 
     L.Add(new Node("forth")); 
     L.PrintNodes(); 
     L.reverse_recursive(); 
     Console.WriteLine("---------------------"); 
     L.PrintNodes(); 
     Console.ReadLine(); 
    } 
} 

public class Node 
{ 
    public object data; 
    public Node next; 
    public Node(object Data) 
    { 
     this.data = Data; 
    } 
} 

public class LinkedList 
{ 
    Node head; 
    Node tail; 
    public void Add(Node n) 
    { 
     if (head == null) 
     { 
      head = n; 
      tail = head; 
     } 
     else 
     { 
      tail.next = n; 
      tail = tail.next; 
     } 

    } 

    public void PrintNodes() 
    { 
     Node temp = head; 

     while (temp != null) 
     { 
      Console.WriteLine(temp.data); 
      temp = temp.next; 
     } 
    } 


    private LinkedList p_reverse_recursive(Node first) 
    { 
     LinkedList ret; 
     if (first.next == null) 
     { 
      Node aux = createNode(first.data); 
      ret = new LinkedList(); 
      ret.Add(aux); 
      return ret; 
     } 
     else 
     { 
      ret = p_reverse_recursive(first.next); 
      ret.Add(createNode(first.data)); 
      return ret; 
     } 

    } 

    private Node createNode(Object data) 
    { 
     Node node = new Node(data); 
     return node; 
    } 

    public void reverse_recursive() 
    { 

     if (head != null) 
     { 
      LinkedList aux = p_reverse_recursive(head); 
      head = aux.head; 
      tail = aux.tail; 
     } 


    } 
} 

希望它可以帮助

Answer 4

另一个变量上一个主题

private void p_reverse_recursive2(Node node) 
    { 
     if (node != null) 
     { 
      Node aux = node.next; 
      node.next = null; 
      p_reverse_recursive2(aux); 
      if (aux != null) 
       aux.next = node; 
     } 

    } 

    public void reverse_recursive() 
    { 

     if (head != null) 
     {    
      Node aux = head; 
      head = tail; 
      tail = aux; 
      p_reverse_recursive2(tail); 
     } 


    } 

Answer 5

变化......

public Node Reverse(Node head) 
{ 
    if(head == null) 
    { 
     return null; 
    } 

    Node reversedHead = null; 
    ReverseHelper(head, out reversedHead); 
    return reversedHead; 
} 

public Node ReverseHelper(Node n, out Node reversedHead) 
{ 
    if(n.Next == null) 
    { 
     reversedHead = n; 
     return n; 
    } 

    var reversedTail = ReverseHelper(n.Next, out reversedHead); 
    reversedTail.Next = n; 
    n.Next = null; 
    return n;  
    } 
} 

Answer 6

我只是在玩类似脑筋急转弯唯一的区别LinkedList类只有头部定义，其余所有节点都链接在那里。所以这里是我的快速和肮脏的递归解决方案：

public Node ReverseRecursive(Node root) 
     { 
      Node temp = root; 
      if (root.next == null) 
       return root; 
      else 
       root = ReverseRecursive(root.next); 
      temp.next = null; 
      Node tail = root.next; 
      if (tail == null) 
       root.next = temp; 
      else 
       while (tail != null) 
       { 
        if (tail.next == null) 
        { 
         tail.next = temp; 
         break; 
        } 
        else 
         tail = tail.next; 
       } 
      return root; 
     }