使用和不使用递归来反转单链表

Question

我是数据结构的新手，我知道这是一个非常常见的问题。但我知道.NET中的LinkedList是双向链接的，所以我将如何在C＃中为单链表编写代码。

有人可以写样本代码吗？

Answer 1

您需要定义一个节点数据结构，其中包含一些数据和对链表中下一个节点的引用。喜欢的东西：

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 
} 

然后，你可以写一个算法遍历以相反的顺序列表，构造一个新的反向列表。

Answer 2

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

Answer 3

使用循环（当前元素：currentNode，变量外循环initialzied：previousNode，nextNode）

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

Answer 4

由于这是有可能的功课，我要去的方式，可能是这个状态相当混乱，以免做所有的工作。希望我的尝试不会让事情变得更混乱（这很有可能）。

当你有一个对列表中的节点的引用（比如说第一个节点）时，还可以引用它后面的节点。您只需要让以下节点引用您的当前节点，同时保留有关下一个节点（及其以前的状态）的足够信息以执行类似的工作。现在唯一棘手的部分是处理边界条件（列表的开始和结束）。

Answer 5

这里是使用递归。

​​

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

以下链接逆转迭代和递归在.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; 
     }