Reverse Linked List

Problem

Given the head of a singly linked list, reverse the list, and return the reversed list.

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Constraints

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Solution

The problem Reverse Linked List can be solved recursively and iteratively. First, a recursive solution reverses the direction of each connection recursively which causes the reversal to begin from the end of the list and progress backwards. Conversely, in an iterative solution, connections are reversed from the start of the list and the reversal of each connection progresses forwards.

Implementation (Recursive)

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

        ListNode *node = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return node;
    }
};

Implementation (Iterative)

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

        while (head != NULL)
        {
            next = head->next;
            head->next = node;
            node = head;
            head = next;
        }

        return node;
    }
};