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

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 ]