###### Solution

Let prev and cur be 2 continuous items of the list:

prev -> cur

We cannot just assign cur->next = prev, because we will lose the information of the next node of cur. So we need to store this information to a node before do the reverse:

• next = cur->next
• cur->next = prev
• prev = cur
• cur = next

This problem has many edge cases:

• the list is empty (i.e head == NULL)
• the list has only one node (i.e. head->next == NULL)
• when to stop reversing loop? => when cur == NULL.
``````    ListNode* reverseList(ListNode* head) {
while (cur) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
``````

Runtime: O(n).

• Recursion solution
``````    ListNode* reverseList(ListNode* head) {
return last;
}
``````

Again we see the power of recursion. Using this technique, we can expand to

• reverse n first item of the list:
``````    ListNode* successor;
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) {
}
``````    ListNode* reverseBetween(ListNode* head, int m, int n) {