Solution For Reverse Linked List

The Reverse Linked List problem on LeetCode is a popular problem that involves reversing the order of a singly linked list. This problem is rated as “Easy” difficulty on the LeetCode website and is a great problem for beginners to practice with.

The problem statement is as follows:

“Reverse a singly linked list.”

Example:

Input: 1->2->3->4->5->NULL

Output: 5->4->3->2->1->NULL

To solve this problem, we can use the iterative or the recursive approach. However, the iterative approach is more efficient and faster.

Iterative Solution

In the iterative solution, we need to traverse the linked list from the beginning and keep reversing the pointers until we reach the end of the list. We can maintain three pointers while traversing the list – current node, previous node, and next node.

Algorithm:

1. Initialize previous node to NULL, current node to head, and next node to NULL.
2. Traverse the linked list with the help of the current node.
3. At each iteration, assign current->next = previous.
4. Move to the next node with the help of the next pointer.
5. Update previous node to the current node.
6. Continue traversing the linked list until the current node is NULL.
7. Return the new head, which is the previous node.

Code:

ListNode* reverseList(ListNode* head) {
ListNode *prev = NULL, *current = head, *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}

Time Complexity: O(n)

Space Complexity: O(1)

The above implementation takes O(n) time complexity, where n is the number of nodes in the linked list. The space complexity of the algorithm is O(1).

Recursive Solution

In the recursive solution, we reverse the list from the current node to the end of the list. Once we reach the end of the list, we update the pointer of the previous node to the current node.

Algorithm:

1. If head is NULL or the list is empty, return head.
2. Recursively reverse the rest of the list from the next node.
3. Once we reach the end of the list, update the pointer for the previous node to the current node.
4. Return the new head, which is the current node.

Code:

ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}

Time Complexity: O(n)

Space Complexity: O(n)

The above implementation takes O(n) time complexity, where n is the number of nodes in the linked list. The space complexity of the algorithm is O(n) because we are using recursion. Each recursive call adds a new call frame to the call stack, which takes up space. This can lead to a stack overflow error for large input sizes.

Conclusion:

In conclusion, the Reverse Linked List problem is a great practice problem for beginners to get started with linked lists. The iterative solution is more efficient and faster since it has a space complexity of O(1). However, the recursive solution is also a good implementation to understand the concept of recursion.

Step by Step Implementation For Reverse Linked List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        // if head is null or head.next is null, return head
        if (head == null || head.next == null) {
            return head;
        }
        
        // create a new node called prev and set it to null
        ListNode prev = null;
        
        // create a new node called curr and set it to head
        ListNode curr = head;
        
        // while curr is not null
        while (curr != null) {
            
            // create a new node called next and set it to curr.next
            ListNode next = curr.next;
            
            // set curr.next to prev
            curr.next = prev;
            
            // set prev to curr
            prev = curr;
            
            // set curr to next
            curr = next;
        }
        
        // return prev
        return prev;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # if head is None or head.next is None:
        #     return head
        #
        # prev = None
        # curr = head
        #
        # while curr is not None:
        #     next = curr.next
        #     curr.next = prev
        #     prev = curr
        #     curr = next
        #
        # return prev

        # recursive solution
        if head is None or head.next is None:
            return head

        reversed_list = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return reversed_list

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // if head is null or head.next is null, return head
    if (!head || !head.next) {
        return head;
    }
    
    // set up three pointers, prev, curr, and next
    let prev = null;
    let curr = head;
    let next = head.next;
    
    // while curr is not null
    while (curr) {
        // set curr.next to prev
        curr.next = prev;
        // move prev and curr pointers forward
        prev = curr;
        curr = next;
        // if next is not null, set next to next.next
        if (next) {
            next = next.next;
        }
    }
    
    // return prev which is now the new head
    return prev;
};

/**
 * 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:
    //Recursive approach
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode* temp = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return temp;
    }
};

//Given the head of a singly linked list, reverse it in-place. 

public class Solution 
{
    public ListNode ReverseList(ListNode head) 
    {
        //edge case - if head is null, return null
        if(head == null)
        {
            return null;
        }
        
        //edge case - if head is the only node in the list, return head
        if(head.next == null)
        {
            return head;
        }
        
        //set up 3 pointers - prev, curr, and next
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;
        
        //iterate through the list until curr is null
        while(curr != null)
        {
            //set next to be curr's next node
            next = curr.next;
            
            //set curr's next node to be prev
            curr.next = prev;
            
            //move prev and curr pointers forward
            prev = curr;
            curr = next;
        }
        
        //set head to be prev (which is now the last node in the list)
        head = prev;
        
        //return the new head of the list
        return head;
    }
}