reverse linked list between given nodes in doubly linked list - algorithm

Question

I am writing code for reversing doubly linked list between given nodes.

given this linked list 1->2->3->4->5,

the function reverse(2,4) should result in 1->4->3->2->5.

the function takes two nodes, but not indices.

Here is what I have. I tried the Eclipse debugger to figure out why this runs indefinitely. for some reasons, I see the nodes being corrupted (Eclipse shows no data when I step through the line marked below)

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

}

Here is my node class

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

}

Is Node current=head,next; a typo (comma) ? It should have been Node current=head.next; — user1952500

David Pérez Cabrera David Pérez Cabrera · Accepted Answer · 2016-01-22T22:56:57

Try with this:

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

Be carefuly with toString method, It's very important, even for debugging!

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

EDIT

It always returns the head node:

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

Example:

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

prints:

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

reverse linked list between given nodes in doubly linked list - algorithm

1 Answers