Description
Reverse a singly linked list.
Examples
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Answer
The main idea of this problem is using two pointers with different speed to find if two pointers will meet. If the given linked list has a cycle in it, then return true . If one of the two pointers reach the edge(NULL) then return false.
Recursive Solution
First decide if the input head is NULL or it does not have the next node. If yes, then return head. The main idea of using recursion to solve the problem is to find the ending of the given linked list and let the last node be the new head of the reversed linked list. After finding the new head, the next thing to do is to let the node before the new head be the next node of the new head, and keep doing these upwards until the outermost function return its result. To find the node before the each node, we need a node called temp to be the nodes in the new reversed linked list, and each time its value equals to the function result of input node’s next. Then the input node is automatically the previous node of temp. And the result of function is temp.
Iterative Solution
The main idea is basically the same with recursive solution. The difference is that recursive solution goes way down and then back upwards but iterative solution is a one-way method that the method goes directly downwards with no turning back. We need two pointers: pre to be the node in the new reversed list initialized as pre->next = head and cur to record the next node in the original linked list initialized as cur = head.
Time Complexity
The complexity of each method is both O(n) with n as the length of the given linked list.
Code
C++
class Solution {
public:
// Recursive version
ListNode* reverseList(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
ListNode* temp = reverseList(head -> next);
head->next->next = head;
head->next = NULL;
return temp;
}
};
class Solution {
public: // Iteration version
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;
}
};
