13.Reverse a Linked List

Various implementation to reverse a linked list

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

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Structure of the linked list is to store data of the node as well as the pointer to the next node's address.

struct node
{
    int data;
    struct node *next;
};

Method 1:-

Function using O(n) time complexity and O(n) space complexity. Using an additional vector to reverse a linked list.

void rev()
{
    if (head == NULL)
    {
        return;
    }
    
    else
    {
        node *p = head;
        vector<int> v;
        while (p != NULL)
        {
            v.push_back(p->data);
            p = p->next;
        }

        node *ptr = head;
        for (int i = v.size() - 1; i >= 0; i--)
        {
            ptr->data = v[i];
            ptr = ptr->next;
        }
    }
}

Method 2:- (using Prev, cur and next pointer)

Function using O(n) time complexity and O(1) space complexity. Making changes in the linked list itself.

class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {

        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        else
        {
            ListNode *prev = NULL;
            ListNode *next = head;
            ListNode *cur = head;

            while (cur != NULL)
            {
                next = cur->next;
                cur->next = prev;
                prev = cur;
                cur = next;
            }

            head = prev;
        }
        return head;
    }
};