Leetcode Linkedlist

206. Reverse Linked List Easy

Link : https://leetcode.com/problems/reverse-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: []

Constraints:

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

Most Optimized C++ solution

/**
 * 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* ans = NULL;
        while(head){
            ListNode* tmp = new ListNode(head->val);
            tmp->next = ans;
            ans = tmp;
            head = head->next;
        }
        return ans;
    }
};

Reversing a Singly-Linked List

This solution focuses on taking a singly-linked list (think of it as a conga line where everyone holds the shoulder of the person in front of them) and reversing the order so that the first person ends up at the end and the last person leads the line.

How It Works

Imagine each person in the line stepping out and forming a new line in the opposite direction. This process ensures that the original order is completely reversed by the end.

1. Starting Point: We begin with an empty new line (ans), which will eventually become the reversed list.

2. Processing Each Person: As long as there are still people in the original line (head), we do the following for each person:

   • Create a new person (tmp) that is a copy of the current leader of the original line.
   • Have this new person point (next) to the current leader of the new line (ans). If the new line is empty, they just stand looking back at the empty space.
   • Move this new person to the front of the new line, making them the new leader (ans = tmp).
   • Move to the next person in the original line (head = head->next).

3. Completing the Reversal: This process repeats until there are no more people in the original line. Each iteration effectively moves the current person from the front of the original line to the front of the new line, reversing the order.

4. Final Step: Once the original line is empty, the new line (ans) is now the original line but in reverse order. We return this as the result.

Technical Explanation

• We initialize ans as NULL to signify the start of the new, reversed list.
• In each iteration of the loop, we:
  • Create a new node (tmp) with the same value as the current node pointed to by head.
  • Set tmp->next to ans, effectively placing it at the beginning of the new list.
  • Update ans to point to tmp, moving the front of the new list forward.
  • Move to the next node in the original list (head = head->next).
• Once head is NULL, indicating we've processed the entire original list, ans points to the head of the newly reversed list.

This algorithm ensures that the list is reversed with a linear time complexity relative to the length of the list, efficiently reordering the elements without modifying their values.