# 8ms C++ Iterative and Recursive Solutions with Explanations

• xWell, since the `head` pointer may also be modified, we create a `new_head` that points to it to facilitate the reverse process.

For the example list `1 -> 2 -> 3 -> 4 -> 5` in the problem statement, it will become `0 -> 1 -> 2 -> 3 -> 4 -> 5` (we init `new_head -> val` to be `0`). Then we set a pointer `pre` to `new_head` and another `cur` to `head`. Then we keep inserting `cur -> next` after `pre` until `cur` becomes the last node. The code is follows.

``````class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* new_head = new ListNode(0);
ListNode* pre = new_head;
ListNode* cur = head;
while (cur && cur -> next) {
ListNode* temp = pre -> next;
pre -> next = cur -> next;
cur -> next = cur -> next -> next;
pre -> next -> next = temp;
}
return new_head -> next;
}
};
``````

This link provides a more concise solution without using the `new_head`. The idea is to reverse one node at a time for the beginning of the list. The rewritten code is as follows.

``````class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* next = head -> next;
head -> next = pre;
}
return pre;
}
};
``````

Well, both of the above solutions are iterative. The hint has also suggested us to use recursion. In fact, the above link has a nice recursive solution, whose rewritten code is as follows.

``````class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* node = reverseList(head -> next);
head -> next -> next = head;
head -> next = NULL;
return node;
}
};
``````

The basic idea of this recursive solution is to reverse all the following nodes after `head`. Then we need to set `head` to be the final node in the reversed list. We simply set its next node in the original list (`head -> next`) to point to it and sets its `next` to be `NULL`.

• Share my codes

iterative

`````` ListNode* reverseList(ListNode* head) {
ListNode *prev = NULL, *cur=head, *tmp;
while(cur){
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
return prev;
}
``````

recursive

``````ListNode* reverseList(ListNode* head) {
auto res = reverseList(head->next);
return res;
}``````

• Thanks for the nice iterative version :-)

• thanks for the decent recursive solution

• In the recursive solution, why is it wrong to use node -> next = head instead of head -> next -> next = head? Thanks a lot!

• @Shane
before reverse:first->second->third.
after reverse:second->first,

• thanks for sharing the recursive method. what is the time complexity of the recursive solution? seems that for each node, we need to reserve all the later nodes, therefore, it is n+(n-1) + ... + 1 so it is O(n^2) ?

• This post is deleted!

• Can someone explain head->next->next = head;?

• @evilcoder nice explain

• @hck94829 pls check evilcoder's explanation, and maybe do a [1,2,3] recursion and I think you will see it.

the trick is that the "head" ptr already points to the second last node, so that head->n is the last one in each recursion, then (head->n)->n point back to the second last node (A.K.A head), then recursively, your head->n =NULL will keep updating till then end node reversely (which is the original head of the list).

Man, I am not good at recursion, so I think the running time is O(n), since the code does depth first, then re-link the first<-second recursively. If I am wrong, any help is appropriated.

Thx

• My solution is quite similar to @tamugaoqi while the initialization is different and takes the place of the first iteration, but it will cause "Time Limit Exceeded" for cases like [1,2]. I wonder why it will cause the problem. Thanks a lot.

``````ListNode* reverseList(ListNode* head) {
if(head == NULL) return NULL;
ListNode* prev = head;
ListNode* temp;
}
return prev;
}``````

• @jywu The problem is your reversed linked list is not null-terminated. You need to create a dummy node that points to the head. After you've finished reversing the linked list in the while loop, set the dummy node to null. This should solve your problem.

• @jagans94 Thanks a lot. This solves my problem.

• Regarding the recursive function, the first time it will actually return is when head->next is NULL. So how can we access head->next->next right after that? Will that not lead to segmentation fault?

• @meadowt After it returns because of head -> next is NULL, the head would be the second last element. so head -> next -> next would set the last one element's next.

• This post is deleted!

• For those of you who got really confused of what the `head->next->next` is all about, here is my rewritten version, a little more verbose, but easy to C++ newbs like me:

``````class Solution {
public:
ListNode* reverseList(ListNode* head) {
} else {
auto new_head = reverseList(head->next); // res is the new reversed head
auto new_tail = head->next; // we just reversed head->next, it now refers to last of new list head
new_tail->next = head; // reverse the normal way
head->next = NULL;  // dereference head->next or it forms a circle
}
}
};
``````

• Since I am still a novice programmer. There is still one little detail that is throwing me off. When I learn linked list, head->next gives me the first valid node that contains a value. In the above example, when we are given head, are we given the first valid node or the "head" that points to the first valid node.

Sorry for the trouble. Thanks for the help!

• @lordofthecode
thanks man! very helpful. :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.