# 206. Reverse Linked List

Reverse a linked list

Thoughts:

1. Using Stack (time limit exceed)
2. Recursively: Find the second from the last node (if it Linked List contains more than two nodes), then reverse current two nodes by first creating a cycle, then cut the forward links (set it to be NULL/nullptr)
3. Having three pointers
1. first record next node and then set current node next to pre
2. repeat for the next step: move pre to head and then move head to next
1. having three pointers with dummy node:
2. pre always inserts cur->next right next to itself

Code 2

``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* node = reverseList(head->next);

return node;
}
};
``````

Code 3

``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode * pre = nullptr;
ListNode *next = head->next;
}
return pre;
}
};
``````

Code 4

``````class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = new ListNode(0);
pre -> next = 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 pre -> next;
}
};
``````

Special Thanks to jianchaolifighter's Solution and and redace85's Solution