使用和不使用遞歸來反轉單鏈表

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