CODEWITHSUNDEEP
javaalgorithmdata-structureslinked-listreverse
Michael
Michael

Reputation: 313

How to reverse a linked list - detailed explanation

Can anyone share a link to the code which explains of how to reverse a linked list? Or could somebody explain the code snippet below?

I've tried to draw/write it, but still don't get how nodes get reversed.

public void reverseList() {
   Node reversedPart = null;
   Node current = head;
   while (current != null) {
       Node next = current.next;
       current.next = reversedPart;
       reversedPart = current;
       current = next;
   }
   head = reversedPart;
}

Upvotes: 2

Views: 369

Answers (2)

Oleksandr Pyrohov
Oleksandr Pyrohov

Reputation: 16246

Let's take a look into a simple example:

1 > 2 > 3 > 4 > 5 > null - our list

Before the while loop: node = 1, head = null

While moving over the list:

1:                 1 > null; node = 1, head = null, node.next = head, head = node

2:             2 > 1 > null; node = 2, head = 1,    node.next = head, head = node

3:         3 > 2 > 1 > null; node = 3, head = 2,    node.next = head, head = node

4:     4 > 3 > 2 > 1 > null; node = 4, head = 3,    node.next = head, head = node

5: 5 > 4 > 3 > 2 > 1 > null; node = 5, head = 4,    node.next = head, head = node

Comments represent the first step of the algorithm:

public Node reverseList(Node head) {
    Node focusNode = head;          // focusNode = 1
    head = null;
    while (focusNode != null) {
      Node parent = focusNode;      // parent = 1
      focusNode = focusNode.next;   // focusNode = 2; moving over the list...
      parent.next = head;           // parent.next = null (1 -> null)
      head = parent;                // head = 1
    }
    return head;
}

Upvotes: 6

Am_I_Helpful
Am_I_Helpful

Reputation: 19168

Firstly, usage of Node next should be avoided inside the while loop to remove any kind of confusion. You should better rename next to nodeNext, and also declare Node nodeNext outside the while loop, and just use nodeNext = current.next; for sorting out any confusion. I think that's your source of confusion.

What this code is doing that it is reversing the direction of links for each node.

Each node's next node direction is being reversed. The direction of pointing of first node towards second node(node ahead to first node originally) is reversed, the first node points to its predecessor, and the node ahead to it points to the first node.

This keeps on repeating till the last node, i.e., current!=null. After that, as soon as the current becomes null, the loop doesn't iterate any further and all the elements have been reversed.

Upvotes: 1

Related Questions