反向鏈接列表

Question

在不使用遞歸的情況下反轉鏈接列表中的問題。

我用這個方法，但是當我嘗試和運行此回了家，我不能打印鏈表的反轉，即使功能看起來好它接着打印方法一樣鏈表它早些時候做過。

有人能幫我理解這裏有什麼問題嗎？

class link { 
    int data; 
    public link nextlink; 

    link(int d1) { 
     data = d1; 
    } 
} 

class List{ 

    link head; 
    link revhead; 

    List(){ 
     head = null; 
    } 

    boolean isEmpty(link head) { 
     return head==null; 
    } 

    void insert(int d1) { 
     link templink = new link(d1); 
     templink.nextlink = head; 
     head = templink; 
    } 

    void printlist(){ 
     link head1 = head; 
     while(!isEmpty(head1)) { 
      System.out.print(head1.data + " "); 
      head1 = head1.nextlink; 
     } 
     System.out.println(); 
    } 

    void reverse() { 
     link previous=null,temp=null; 
     while(isEmpty(head)) { 
      temp = head.nextlink; 
      head.nextlink = previous; 
      previous = head; 
      head = temp; 
     } 
    } 

} 

public class LinkedList { 

    public static void main(String[] args) { 

     List list1 = new List(); 

     list1.insert(10); 
     list1.insert(20); 
     list1.insert(30); 
     list1.insert(40); 
     list1.insert(50); 
     list1.printlist(); 
     list1.reverse(); 
     list1.printlist(); 
    } 
} 

Answer 1

你的代碼有兩個問題。一：你檢查isEmpty（頭），你應該檢查！isEmpty（頭）。其次：當你解決第一個問題時，當循環終止時，'head'變爲null。

正確的代碼修復了以上兩個問題：

void reverse() { 
    link previous = null, temp = null; 
    while (!isEmpty(head)) { 
     temp = head.nextlink; 
     head.nextlink = previous; 
     previous = head; 
     if (temp == null) { 
      break; 
     } 
     head = temp; 
    } 

} 

Answer 2

檢查條件： 一段時間（的isEmpty（頭））

你忘了加上 「！」你的意思雖然不是空的......

Answer 3

考慮遞歸方法在打印鏈接時的作用。實際上它並沒有做任何事情（即將每個調用放在堆棧上，然後當達到基本情況時，它會從堆棧中彈出元素）。

你有什麼非堆棧結構可用於存儲列表的反向，然後讓你打印出來？

Answer 4

更正後的代碼逆轉鏈表沒有遞歸。

class Link { 

    int data; 
    public Link nextLink; 

    Link(int d1) { 
     data = d1; 
    } 
} 

class List { 

    Link head; 
    Link revhead; 

    List() { 
     head = null; 
    } 

    boolean isEmpty(Link head) { 
     return head == null; 
    } 

    void insert(int d1) { 
     Link tempLink = new Link(d1); 
     tempLink.nextLink = head; 
     head = tempLink; 
    } 

    void printlist() { 
     Link head1 = head; 
     while (!isEmpty(head1)) { 
      System.out.print(head1.data + " "); 
      head1 = head1.nextLink; 
     } 
     System.out.println(); 
    } 

    void reverse() { 
     Link previous = null, temp = null; 
     while (!isEmpty(head)) { 
      temp = head.nextLink; 
      head.nextLink = previous; 
      previous = head; 
      head = temp; 
     } 

     head = previous; 
    } 
} 

public class Main { 

    public static void main(String[] args) { 

     List list1 = new List(); 

     list1.insert(10); 
     list1.insert(20); 
     list1.insert(30); 
     list1.insert(40); 
     list1.insert(50); 
     list1.printlist(); 
     list1.reverse(); 
     list1.printlist(); 
    } 
} 

Answer 5

class Node { 
    Node next; 
    int value; 

    public Node() { 
    } 

    public Node(Node next, int value) { 
     super(); 
     this.next = next; 
     this.value = value; 
    } 

    public Node getNext() { 
     return next; 
    } 

    public void setNext(Node next) { 
     this.next = next; 
    } 

    public int getValue() { 
     return value; 
    } 

    public void setValue(int value) { 
     this.value = value; 
    } 

} 

public class Linkedlist { 
    private Node head = null; 

    public Linkedlist(Node head) { 
     this.head = head; 
    } 

    public void iterate() { 
     Node current = head; 
     while (current != null) { 
      System.out.println(current.getValue()); 
      current = current.getNext(); 
     } 
    } 

    public void reverse() { 
     Node current = head; 
     Node prev = null; 
     while (current != null) { 
      Node temp = current.next; 
      current.next = prev; 
      prev = current; 
      current = temp; 
     } 
     head = prev; 
    } 

    public static void main(String[] args) { 
     Node n = new Node(null, 10); 
     Node n1 = new Node(n, 20); 
     Node n2 = new Node(n1, 30); 
     Node n3 = new Node(n2, 40); 
     Node n4 = new Node(n3, 50); 
     Node n5 = new Node(n4, 60); 
     Linkedlist linkedlist = new Linkedlist(n5); 
     linkedlist.iterate(); 
     linkedlist.reverse(); 
     System.out.println("------------------REVERSED---------------------"); 
     linkedlist.iterate(); 

    } 
}