HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Critique Request: Reversing a singly linked list

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
critiquerequestsinglylistlinkedreversing

Problem


  • I find the tail in the first while loop and store it in the tailEnd node.



  • I update the tail to the previous node and change the tail.next to point to the previous node.



  • Once head.next.next == head, the reversing is finished.



package LinkedLists;

class Reverse {

    public static LinkedList reverse(LinkedList Node) {
        LinkedList head = Node;

        while (Node.next != null) {
            Node = Node.next;
        }

        LinkedList tail = Node;
        LinkedList tailEnd = Node;

        Node = head;

        while (Node.next != null) {
            if (head.next.next == head) {
                head.next = null;
                return tailEnd;
            }

            while (Node.next != tail) {
                Node = Node.next;
            }
            tail.next = Node;
            tail = Node;
            Node = head;
        }

        return tailEnd;
    }

    public static void main(String[] args) {
        LinkedList HeadNode = new LinkedList(1);
        LinkedList Node1 = new LinkedList(2);
        LinkedList Node2 = new LinkedList(3);
        LinkedList Node3 = new LinkedList(4);
        LinkedList TailNode = new LinkedList(5);
        HeadNode.next = Node1;
        Node1.next = Node2;
        Node2.next = Node3;
        Node3.next = TailNode;
        TailNode.next = null;
        LinkedList revHead = Reverse.reverse(HeadNode);
        while (revHead != null) {
        System.out.println(revHead.data);
        revHead = revHead.next;
        }
    }
}

Solution

This could be done simpler and more efficiently. This only requires one iteration through the list:

public static LinkedList reverse(LinkedList Node) {
    LinkedList previous = null;
    while (Node != null) {
        LinkedList next = Node.next;
        Node.next = previous;
        previous = Node;
        Node = next;
    }
    return previous;
}


On another note, it is more common for package names to be all lowercase and for local variable and parameter names to be camel case. For example:

package linkedlists;

public static LinkedList reverse(LinkedList node) {

LinkedList headNode = new LinkedList(1);

Code Snippets

public static LinkedList reverse(LinkedList Node) {
    LinkedList previous = null;
    while (Node != null) {
        LinkedList next = Node.next;
        Node.next = previous;
        previous = Node;
        Node = next;
    }
    return previous;
}
package linkedlists;

public static LinkedList reverse(LinkedList node) {

LinkedList headNode = new LinkedList(1);

Context

StackExchange Code Review Q#25696, answer score: 4

Revisions (0)

No revisions yet.