# 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;
    }
};