java - 双向链表中给定节点之间的反向链表 - 算法

Question

我正在编写代码来反转给定节点之间的双向链表。

给定这个链表1->2->3->4->5，

函数 reverse(2,4) 的结果应该是1->4->3->2->5。

该函数采用两个节点，但不采用索引。

这是我的。我尝试了 Eclipse 调试器来找出它无限期运行的原因。由于某些原因，我看到节点已损坏(当我单步执行下面标记的行时，Eclipse 未显示任何数据)

public static void reverse(Node head, Node tail){
        Node prev=head.prev;
        Node current=head,next;
        while(current!=tail.next){
            next = current.next;
            current.next=prev;
            current.prev=next; //No data stepping after this point
            prev=current;
            current=next;
        }
    }

public static void main(String... args){
        Node one = new Node(1);
        Node two = new Node(2);
        Node three = new Node(3);
        Node four = new Node(4);
        Node five = new Node(5);

        five.setNodes(four, null);
        four.setNodes(three, five);
        three.setNodes(two,four);
        two.setNodes(one,three);
        one.setNodes(null, two);

        System.out.println("before reversing...");
        System.out.println(one);

        System.out.println("After reversing...");
        reverse(two,four);
        System.out.println(one);

}

这是我的节点类

class Node {
     Node prev;
     Node next;
     int data;

     public Node(Node prev, Node next, int val){
         this.prev=prev;
         this.next=next;
         this.data=val;
     }

     public Node(int val){
         this(null,null,val);
     }

     public void setNodes(Node prev, Node next){
         this.next=next;
         this.prev=prev;
         }

     public String toString(){
         String toReturn = "[ " + this.data;

         Node current=this.next;
         while (current!=null){
             toReturn+=" -> " + current.data;
             current=current.next;
         }
         toReturn+=" ]";
         return toReturn;
     }

}

Answer 1

试试这个:

public static void reverse(Node head, Node tail) {
    Node first = head;
    Node last = tail;
    while (first != last && first.prev != last) {
        Node preFirst = first.prev;
        Node postFirst = first.next;
        Node preLast = last.prev;
        Node postLast = last.next;
        if (preFirst != null) {
            preFirst.next = last;
        }
        if (postLast != null) {
            postLast.prev = first;
        }
        last.prev = preFirst;
        first.next = postLast;
        if (last != postFirst){
            last.next = postFirst;
            postFirst.prev = last;
            first.prev = preLast;
            preLast.next = first;
            first = postFirst;
            last = preLast;
        } else {
            last.next = first;
            first.prev = last;
        }
    }
}

小心使用 toString 方法，它非常重要，即使对于调试也是如此!

public String toString(){
     String toReturn = "[ " + this.data;

     Node current=this.next;
     while (current!=null && current != this){ // <- cycle protection
         toReturn+=" -> " + current.data;
         current=current.next;
     }
     toReturn+=" ]";
     return toReturn;
 }

编辑

它总是返回头节点:

public static Node reverse(Node head, Node tail) {
    Node first = head;
    Node last = tail;
    while (first != last && first.prev != last) {
        Node preFirst = first.prev;
        Node postFirst = first.next;
        Node preLast = last.prev;
        Node postLast = last.next;
        if (preFirst != null) {
            preFirst.next = last;
        }
        if (postLast != null) {
            postLast.prev = first;
        }
        last.prev = preFirst;
        first.next = postLast;
        if (last != postFirst){
            last.next = postFirst;
            postFirst.prev = last;
            first.prev = preLast;
            preLast.next = first;
            first = postFirst;
            last = preLast;
        } else {
            last.next = first;
            first.prev = last;
        }
    }
    Node result = tail;
    while (result.prev != null){
        result = result.prev;
    }
    return result;
}

例子:

public static void main(String... args) {
    Node one = new Node(1);
    Node two = new Node(2);
    Node three = new Node(3);
    Node four = new Node(4);
    Node five = new Node(5);

    five.setNodes(four, null);
    four.setNodes(three, five);
    three.setNodes(two, four);
    two.setNodes(one, three);
    one.setNodes(null, two);

    System.out.println("before reversing...");
    System.out.println(one);

    System.out.println("After reversing...");
    one = reverse(one, three);
    System.out.println(one);
}

打印:

before reversing...
[ 1 -> 2 -> 3 -> 4 -> 5 ]
After reversing...
[ 3 -> 2 -> 1 -> 4 -> 5 ]