# 206. Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
# Solution
Approach 1: Iteration.
Approach 2: Recursion.
# Code (Python)
Approach 1:
def reverseList(self, head: ListNode) -> ListNode:
# iterative solution: for all 'next' pointers, keep the nodes on both sides and modify the pointer. Right before the modification remember what the next node is supposed to be.
if not head or not head.next:
return head
first, second = None, head
while second:
third = second.next
second.next = first
first = second
second = third
return first
Approach 2:
def reverseList(self, head: ListNode) -> ListNode:
# recursive solution: reverse head.next, and grab hold of the new tail by head.next
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
head.next.next = head # head.next is now the new tail, and we want the new tail's next pointer to point to the head
head.next = None
return new_head
# Code (C++)
Approach 1:
/**
* 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* curr = head;
ListNode* prev = NULL;
while (curr)
{
ListNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
Approach 2:
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head && head->next)
{
ListNode *nextHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return nextHead;
}
return head;
}
};