-2

在不使用递归的情况下反转链表的问题。

我使用了这种方法，但是当我尝试在家里运行它时，即使该功能看起来不错，我也无法打印链表的反向它继续以与之前相同的方式打印链表。

有人可以帮我理解这里有什么问题吗？

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();
     }
}
4

5 回答 5

4

您的代码中有两个问题。一：你检查 isEmpty(head)，你应该检查 !isEmpty(head)。第二：当你解决第一个问题时，循环终止时'head'变为空。

修复上述两个问题的正确代码：

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

}
于 2012-05-17T17:58:53.557 回答
0

检查您的情况：while (isEmpty(head))

您忘记添加“！” 你的意思是虽然不是空的......做

于 2012-05-17T17:56:30.657 回答
0

考虑打印链接时递归方法的作用。它实际上没有做任何事情，直到它拥有所有它们（即，它将每个调用放在堆栈上，然后当达到基本情况时，它从堆栈中弹出元素）。

您有哪些现成的非堆栈结构可用于存储列表的反向，然后让您将其打印出来？

于 2012-05-17T17:58:00.530 回答
0

用于在不递归的情况下反转链接列表的更正代码。

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();
    }
}
于 2012-05-18T06:47:29.253 回答
-1 
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();

    }
}
于 2016-02-21T14:10:21.407 回答