Last updated on July 16th, 2024 at 05:37 am

Here, We see Reverse Linked List problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Linked List

Companies

Adobe, Amazon, Apple, Bloomberg, Facebook, Microsoft, Snapchat, Twitter, Uber, Yahoo, Yelp, Zenefits

Level of Question

Easy

Reverse Linked List LeetCode Solution

Problem Statement

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

Example 1: (fig-1)
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2: (fig-2)
Input: head = [1,2]
Output: [2,1]

Example 3:
Input: head = []
Output: []

1. Reverse Linked List Leetcode Solution C++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = new ListNode(0), *cur = head;
        pre -&gt; next = head;
        while (cur &amp;&amp; cur -&gt; next) {
            ListNode* temp = pre -&gt; next;
            pre -&gt; next = cur -&gt; next;
            cur -&gt; next = cur -&gt; next -&gt; next;
            pre -&gt; next -&gt; next = temp;
        }
        return pre -&gt; next;
    }
};

1.1 Explanation

Initialize Pointers:
- Create a dummy node pre with a value of 0 and set its next pointer to head.
- Initialize a pointer cur to the head of the list.
Iterate and Reverse:
- While cur and cur->next are not null, perform the following steps:
  - Store the node pointed to by pre->next in temp.
  - Update pre->next to point to cur->next.
  - Update cur->next to point to the node after cur->next.
  - Update pre->next->next to point to temp.
Return Result: Return the node pointed to by pre->next, which is the new head of the reversed list.

1.2 Time Complexity

O(n).

1.3 Space Complexity

O(1).

2. Reverse Linked List Leetcode Solution Java

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode nextNode=head.next;
        ListNode newHead=reverseList(nextNode);
        nextNode.next=head;
        head.next=null;
        return newHead;
    }
}

2.1 Explanation

Base Cases: If the list is empty or has only one node, return head as is.
Recursive Call: Recursively call reverseList on the next node and store the new head of the reversed list in newHead.
Reverse Links: Reverse the link by setting nextNode.next to head and head.next to null.
Return Result: Return newHead, which is the new head of the reversed list.

2.2 Time Complexity

O(n) due to the recursive calls.

2.3 Space Complexity

O(n) due to the recursion stack.

3. Reverse Linked List Leetcode Solution JavaScript

var reverseList = function(head) {
    let [prev, current] = [null, head]
    while(current) {
        [current.next, prev, current] = [prev, current, current.next]
    }
    return prev
};

3.1 Explanation

Initialize Pointers: Initialize prev to null and current to head.
Iterate and Reverse: While current is not null, perform the following steps:
- Reverse the link by setting current.next to prev.
- Move prev to current.
- Move current to the next node in the list.
Return Result: Return prev, which is the new head of the reversed list.

3.2 Time Complexity

O(n) because each node is visited once.

3.3 Space Complexity

O(1) due to the iterative approach.

4. Reverse Linked List Leetcode Solution Python

class Solution(object):
    def reverseList(self, head):
        prev = None
        curr = head

        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev

4.1 Explanation

Initialize Pointers: Initialize prev to None and curr to head.
Iterate and Reverse: While curr is not null, perform the following steps:
- Store the next node in next.
- Reverse the link by setting curr.next to prev.
- Move prev to curr.
- Move curr to next.
Return Result: Return prev, which is the new head of the reversed list.

4.2 Time Complexity

O(n).

4.3 Space Complexity

O(1) due to the iterative approach.