How can I reverse a linked list?

Question

Consider:

 Node reverse(Node head) {
    Node previous = null;
    Node current = head;
    Node forward;

    while (current != null) {
        forward = current.next;
        current.next = previous;
        previous = current;
        current = forward;
    }

    return previous;
}

How exactly is it reversing the list?

I get that it first sets the second node to forward. Then it says current.next is equal to a null node previous. Then it says previous is now current. Lastly current becomes forward?

I can't seem to grasp this and how it's reversing. Can someone please explain how this works?

Thorn

from __future__ import braces ? – G

my fault..fixed to java! – Thorn

1. This code does not seem to be python... 2. list reverse is a basic algorithm, you can find many related material on web – Attract

When you have a bug or cannot understand what your code is doing, the first thing you should do is use your debugger. (That's what it is for) – Fagaceous

I would draw up a little 3-node linked list on a piece of paper, and just go through the algorithm step by step, see what happens. You could do the same thing in a debugger, but doing it on paper will force you to really think about how each piece of state is changing. – Mixed

Remember first you have to store next node(forward) to preserve link – Rooseveltroost

Techlead is that you??? – Tova

Answer 1

Blackheart

Only the Techlead knows that. How can you know that... xaxa – Tova

Answer 2

You reverse the list iteratively and always have the list in the interval [head, previous] correctly reversed (so current is the first node that has its link not set correctly). On each step you do the following:

• You remember the next node of current so that you can continue from it
• You set the link of current to be pointing to previous, which is the correct direction if you think about it
• You change previous to be current, because now current also has its link set correctly
• You change the first node that does not have its link set correctly to be the one remembered in the first step

If you do that for all the nodes, you can prove (with induction for instance) that the list will be correctly reversed.

Griskin

Answer 3

The code simply walks the list and inverts the links until it reaches the previous tail, which it returns as the new head.

Before:

Node 1 (Head) -> Node 2 -> Node 3 -> Node 4 (Tail) -> null

After:

   null <- Node 1 (Tail) <- Node 2 <- Node 3 <- Node 4 (Head)

Daye

I think he wanted to understand the "code". The meaning of "reverse" is quite obvious, the "code" isn't. – Blackheart

Answer 4

public Node getLastNode()
{
    if(next != null)
        return next.getLastNode();
    else
        return this;
}

public Node reverse(Node source)
{
    Node reversed = source.getLastNode();
    Node cursor = source;

    while(cursor != reversed)
    {
        reversed.addNodeAfter(cursor.getInfo());
        cursor = cursor.getNodeAfter();
    }

    source = reversed;
    return source;
}

Sudderth

Answer 5

I call it "cherry picking". The idea is to minimize the number of swaps. Swapping happens between a near and far index. It's a twp-pass algorithm.

    (Odd length)  A -> B -> C -> D -> E
    (Even length) A -> B -> C -> D

    Pre-Condition: N >= 2

    Pass 1: Count N, the number of elements

    Pass 2:
            for(j=0 -> j<= (N/2 -1))
            {
              swap(j, (N-1)-j)
            }

Example 1:

   For above Odd length list, N = 5 and there will be two swaps

      when j=0, swap(0, 4) // Post swap state: E B C D A
      when j=1, swap(1, 3) // Post swap state: E D C B A


   The mid point for odd length lists remains intact.

Example 2:

   For above Even length list, N = 4 and there will be two swaps

      when j=0, swap(0, 3) // Post swap state: D B C A
      when j=1, swap(1, 2) // Post swap state: D C B A

• Swapping applies to data only, not to pointers, and there might be any sanity checks missed, but you got the idea.

Plop

Nice. However, one precondition is we need to know the length of the linked list. – Valuate

Yes, that's why its 2-pass. But the no of swaps required in 2nd pass is always <= N/2 .. So the complexity is still O ( N + N /2 ) or linear. – Plop

Answer 6

  list_t *reverse(list_t *a)
  {
    list_t *progress = NULL;
    while(a)
    {
      list_t *b; //b is only a temporary variable (don't bother focusing on it)
      b = a->next;
      a->next = progress; // Because a->next is assigned to another value,
                          // we must first save a->next to a different
                          // variable (to be able to use it later)
      progress = a; // progress is initially NULL (so a->next = NULL
                    // (because it is the new last element in the list))
      a = b; // We set a to b (the value we saved earlier, what
             // a->next was before it became NULL)
      /*
        Now, at the next iteration, progress will equal a, and a will equal b.
        So, when I assign a->next = progress, I really say, b->next = a.
        and so what we get is: b->a->NULL.
        Maybe that gives you an idea of the picture?

        What is important here is:
          progress = a
        and
          a = b

        Because that determines what a->next will equal:
          c->b->a->0

        a's next is set to 0
        b's next is set to a
        c's next is set to b
      */
    }
    return progress;
  }

Anora

Answer 7

The easiest way to think about it is to think like this:

1. First add the head of the list to a new linked list.
2. Keep iterating through the original and keep adding the nodes before the head of the new linked list.

Diagram:

Initially:

Original List -> 1 2 3 4 5
New List -> null

1st Iteration

Original List -> 1 2 3 4 5
New List -> 1->null [head shifted to left, now newHead contains 1 and points to null]

2nd Iteration

Original List -> 1 2 3 4 5
New List -> 2-> 1->null [head shifted to left, now newHead contains 2 and points to next node which is 1]

3rd Iteration

Original List -> 1 2 3 4 5
New List ->3 -> 2-> 1->null [head shifted to left, now newHead contains 2 and points to next node which is 1]

Now it keeps looping through till the end. So finally the new list becomes:

  New List->  5 -> 4 -> 3 -> 2 -> 1 -> null

The code for the same should be like this (made it easy to understand):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

public ListNode reverseList(ListNode head) {
    if(head == null) {
        return null;
    }

    if(head.next == null) {
        return head;
    }

    ListNode current = head;
    ListNode previous = new ListNode(head.val);
    previous.next = null;

    while(current.next != null) {
        current = current.next;
        previous = addBeforeHead(current, previous);
    }

    return previous;
}

private ListNode addBeforeHead(ListNode node, ListNode head) {
    if (node == null) return null;
    ListNode temp = new ListNode(node.val);

    temp.next = head;
    head = temp;

    return head;
}

Cristoforo

Why allocate new ListNodes when the task is not return a list with the values in reverse order, but reverse a linked list? (Why not allocate a new node for a single-element list? You can combine the special cases: if (head == null || head.next == null) return head;) – Tripersonal

@Tripersonal Yes that can be done. But the way I did makes it easier to understand and also does not take up extra memory. – Cristoforo

Perhaps turn syntax highlighting off? – Frostbitten

Answer 8

Reversing a singly-linked list using iteration:

current = head // Point the current pointer to the head of the linked list

while(current != NULL)
{
    forward = current->link; // Point to the next node
    fforward = forward->link; // Point the next node to next node
    fforward->link = forward; // 1->2->3,,,,,,,,,this will point node 3 to node 2
    forward->link = current; // This will point node 2 to node 1

    if(current == head)
        current->link = NULL; // If the current pointer is the head pointer it should point to NULL while reversing

    current = current->link; // Traversing the list
}
head = current; // Make the current pointer the head pointer

Cadmann

Answer 9

The basic idea is to detach the head node from the first list and attach it to the head of a second list. Keep repeating until the first list is empty.

Pseudocode:

function reverseList(List X) RETURNS List
   Y = null
   WHILE X <> null
      t = X.next
      X.next = Y
      Y = X
      X = t
   ENDWHILE
   RETURN Y
ENDfunction

If you wish to leave the original list undisturbed then you can code a copying version recursively with the use of a helper function.

function reverseList(List X) RETURNS List
   RETURN reverseListAux(X, null)
ENDfunction

function reverseListAux(List X, List Y) RETURNS List
   IF X = null THEN
       RETURN Y
   ELSE
       RETURN reverseListAux(X.next, makeNode(X.data, Y))
ENDfunction

Note that the helper function is tail recursive. This means that you can create a copying reversal using iteration.

function reverseList(List X) RETURNS List
   Y = null
   WHILE X <> null
     Y = makeNode(x.data, Y)
     X = X.next   
   ENDWHILE
   RETURN Y
ENDfunction

Upanddown

Answer 10

Implementation of a singly-linked list reversal function:

struct Node
{
    int data;
    struct Node* link;
}

Node* head = NULL;

void reverseList()
{
    Node* previous, *current, *next;
    previous = NULL;
    current = head;

    while(current != NULL)
    {
        next = current-> link;
        current->link = previous;
        previous = current;
        current = next;
    }

    head = previous;
}

Paleoecology

Answer 11

Here is a simple function to reverse a singly linked list

// Defining Node structure


public class Node {
int value;
Node next;


public Node(int val) {
    
    this.value=val;
}

}

public LinkedList reverse(LinkedList list) {
    
    if(list==null) {
        
        return list;
    }
    
    Node current=list.head;
    Node previous=null;
    Node next;
    
    while(current!=null) {
        
        next=current.next;
        
        current.next=previous;
        
        previous=current;
        
        current=next;
        
    }
    
    list.head=previous;
    
    return list;
    
    
    
    
}

For better understanding, you can watch this video https://youtu.be/6SYVz-pnVwg

Runnel

Answer 12

If you want to use recursion:

         class Solution {

         ListNode root=null;

         ListNode helper(ListNode head)
         {
             if (head.next==null)
             {  root= head;
                 return head;}

             helper (head.next).next=head;
             head.next=null;

             return head;
         }


         public ListNode reverseList(ListNode head) {
             if (head==null)
             {
                 return head;
             }
             helper(head);
             return  root;

         }
     }

Recreant

Answer 13

public void reverseOrder() {
    if(head == null) {
        System.out.println("list is empty");
    }
    else {
    Node cn = head;
    int count = 0;
    while (cn != null) {
        count++;
        cn = cn.next;
    }
    Node temp;
    for(int i = 1; i<=count; i++) {
        temp = head;
        for(int j = i; j<count; j++) {
            temp = temp.next;
        }
        System.out.print(temp.data+" ->");
    }
    System.out.print("null");
}
}

Ceramist