Reversing linked list iteratively and recursively

Implement the reversal of a singly linked list iteratively and recursively.


Reversing linked list can be done both iteratively and recursively. In my opinion, the iterative solution should be more efficient and less memory overhead than its recursive counterpart (Imagine reversing a link list that has one million elements recursively! It would quickly run out of stack space).

The recursive solution can be coded in fewer lines of code, but is harder to code correctly. On the other hand, the iterative solution requires more code but is easier to verify.

1) The iterative way:

Please do note that the head pointer is passed in by reference. If you have trouble understanding the syntax, think the pointer as a type, and an & sign followed by a type signifies the variable is passed by reference. The head pointer must be passed in by reference whenever there might be a change to the head pointer itself!

2) The recursive way:

Can you see why the head pointer is eventually updated to point to the last element of the list? Try to draw a diagram and see how the rest pointer changes when the recursion exits. (Hint: the rest pointer points to the last element and does not change).

VN:F [1.9.22_1171]
Rating: 4.3/5 (97 votes cast)
Reversing linked list iteratively and recursively, 4.3 out of 5 based on 97 ratings

49 thoughts on “Reversing linked list iteratively and recursively

  1. 1337c0d3r

    No specific reason to use reference, they mean the same thing other than semantic differences.

    Reference is a C++ feature that's not in C. In C, if you need to modify the real value of the pointer (but not the copy of the value), you need to pass in a pointer to pointer.

    But in C++, in addition to the method mentioned, you can also pass in a reference to a pointer in order to modify the pointer's value.

    VA:F [1.9.22_1171]
    -1
  2. 1337c0d3r

    Thanks for checking the code, it's always great to have someone looking at my code and make sure it's correct.

    I've just verified the code using a program, with your example of two nodes. It appears to be working.

    VA:F [1.9.22_1171]
    0
  3. 1337c0d3r

    If you use node* but not node**, the pointer used in the function will be a copy of the original pointer. You are not able to modify the original pointer. Then, how are you going to change the head pointer to point to the last element after you reverse the list?

    VA:F [1.9.22_1171]
    +2
  4. Anonymous

    I imagine Anonymous was thinking of this as returning a pointer to the new head, in which case you would only need node*.

    VA:F [1.9.22_1171]
    +1
  5. johny

    Hi, 1337:

    I must admit that I have had a hard time in understanding the recursive code to reverse a linked list. Even as I drew the diagram, I can’t understand why the “rest” pointer is unchanged and always pointing to the last element of the linked list.

    Luckily, I downloaded a tutorial (http://cslibrary.stanford.edu/105/LinkedListProblems.pdf) for LinkedList as you provided here (http://www.ihas1337code.com/2010/09/more-linked-list-problems-to-practice.html), in which I found the similar problem and a similar solution:

    void RecursiveReverse(struct node** headRef) {
    struct node* first;
    struct node* rest;

    if (*headRef == NULL) return; // empty list base case

    first = *headRef; // suppose first = {1, 2, 3}
    rest = first->next; // rest = {2, 3}

    if (rest == NULL) return; // empty rest base case

    RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
    // after: rest = {3, 2}

    first->next->next = first; // put the first elem on the end of the list
    first->next = NULL; // (tricky step — make a drawing)

    *headRef = rest; // fix the head pointer
    }

    Here, the function’s parameter list “void RecursiveReverse(struct node** headRef)” and the function call “RecursiveReverse(&rest)” implies the pointer “rest” would be changed itself through the call.

    Suddenly, everything is clear.

    Looking back, my initial confuse is due to my unfamilarity with C++ (I was working in embedded area, using C).

    Although you have defined the recursive function as “void reverse(Node* & p)” and emphasized this reference is necessary when changes to the input parameter is intended to propagate back to its caller, I simply forgot this fact in going through your recursive solution. In reading your call of “reverse(rest)”, I didn’t realized that a reference has been passed in and “rest” would be modified.

    What an ignorance!

    VA:F [1.9.22_1171]
    +2
    1. fengse

      The thing makes me confused a lot is that in 1337’s code, p->next->next = p. I am assuming that at this point, the *p had already be changed from the last recursion call. So why it work.. anyone can help me figure out?

      VN:F [1.9.22_1171]
      0
  6. reader

    @1337c0d3r:The recursive approach is really nice but I was wondering the following:The iterative solution can be translated (almost) as is to a recursive method.How come you did not do it that way?

    VA:F [1.9.22_1171]
    0
    1. Zhi Zhou

      Yeah, I don’t think it’s needed in this code. The code does not update its head pointer to point to the last node

      VA:F [1.9.22_1171]
      0
      1. Zhi Zhou

        I was wrong. since rest is passed as a reference, it’s value is changed in all first (n – 1) recursive calls by the base call. So it will point to the last node returning from each recursion. (see Hint in the original code).

        VA:F [1.9.22_1171]
        0
  7. k10world

    C# code –

    VA:F [1.9.22_1171]
    0
  8. Tunan

    In the recursion version, are the last two lines (p->next = NULL; p = rest;) actually needed? As the function is returned after them, p is no more used.

    VA:F [1.9.22_1171]
    +2
  9. roger

    following piece of code takes the advantage of an implicit stack

    VN:F [1.9.22_1171]
    0
  10. sankalp

    simple recusive code:

    node* reverse(node* t)
    {
    if(t->next!=NULL)
    {
    reverse(t->next)->next=t;
    t->next=NULL;
    }
    return t;
    }

    if your using classes use scope resolution for node* i.e. is c::node*
    this may not work i.e. returing structures while using templates

    VN:F [1.9.22_1171]
    0
  11. moussa

    VA:F [1.9.22_1171]
    0
  12. ram

    Please see this solution in java
    I have used start as a variable to change start of the node

    public static Link reverse(Link link){

    if(link.next==null){
    start=link;
    return link;
    }
    else{

    temp=reverse(link.next);
    link.next=null;
    temp.next=link;
    temp=link;
    return temp;

    }

    }

    VA:F [1.9.22_1171]
    +1
  13. shivi

    VA:F [1.9.22_1171]
    +1
  14. lcn

    Crystal clear Java code:

    VN:F [1.9.22_1171]
    +6
    1. Su

      I guess we can do this better:

      VA:F [1.9.22_1171]
      +1
  15. lin17

    VN:F [1.9.22_1171]
    +2
  16. hina

    @1337c0d3r : I really like your posts…They are so easy to understand. I would just like to dedicate a quote by Albert Einstein for your posts :
    “If you can’t explain it simply, you don’t understand it well enough.”
    Your explanation is really too good….:)))

    I have a small doubt in the recursive version here……in the recursive call to reverse(), shouldn’t it be reverse(&rest) instead of reverse(rest).

    VA:F [1.9.22_1171]
    0
  17. David Shuai Lee

    //recursively
    public void reverseRecursive(Node currentNode){
    if(currentNode == null){
    return;
    }
    if(currentNode.nextNode == null){
    head = currentNode;
    return;
    }
    reverseRecursive(currentNode.nextNode);
    currentNode.nextNode.nextNode = currentNode;
    currentNode.nextNode = null;
    }

    //iteratively
    public void reverse(ReverseSinglyLinkedList singlyLinkedList){
    if(singlyLinkedList.isEmpty()){
    return;
    }
    Node currentNode = head;
    Node nextNode = head.nextNode;
    Node markNode;
    head.nextNode = null;
    while(nextNode!=null){
    markNode = nextNode.nextNode;
    nextNode.nextNode = currentNode;
    currentNode = nextNode;
    nextNode = markNode;
    }
    head = currentNode;
    }

    VA:F [1.9.22_1171]
    0
  18. someone

    VA:F [1.9.22_1171]
    0
  19. Pingback: 翻转链表-迭代和递归双版本 | 易鸣

  20. Pingback: 翻转链表 - 博客园

  21. Pingback: 翻转链表-迭代和递归双版本 – soyscut | 查问题

  22. Lal

    public ListNode Reverse(ListNode list){

    /* If the list is empty */
    if(list == null)
    return null;

    /* If the list has only one node */
    if(list.next == null)
    return list;

    ListNode secondElement = list.next;
    list.next = null;
    ListNode reverseRest = Reverse(secondElement);

    /* Join the two lists */
    secondElement.next = list;
    return reverseRest;
    }

    VA:F [1.9.22_1171]
    0
  23. Pingback: LeetCode | Technical interview solutions

  24. Guest1122

    I found this code intuitive to write… But this is O(n^2)..

    VA:F [1.9.22_1171]
    0
  25. vlsireddy

    .

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*