Reverse Linked List

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        return prev;
    }
};

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

                                            
class Solution:
    def reverseList(self, head):
        prev = None
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        return prev

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

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

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
 function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let current: ListNode | null = head;
    
    while (current !== null) {
        const nextTemp: ListNode | null = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    
    return prev;
}

                                            
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    
    /**
     * @param ListNode $head
     * @return ListNode
     */
    function reverseList($head) {
        $prev = null;
        $current = $head;
        while ($current != null) {
            $nextNode = $current->next;
            $current->next = $prev;
            $prev = $current;
            $current = $nextNode;
        }
        return $prev;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { val = 0; next = nil }
 *     public init(_ val: Int) { self.val = val; next = nil }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var prev: ListNode? = nil
        var current = head
        
        while let node = current {
            let nextTemp = node.next
            node.next = prev
            prev = node
            current = nextTemp
        }
        
        return prev
    }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    current := head
    for current != nil {
        nextTemp := current.Next
        current.Next = prev
        prev = current
        current = nextTemp
    }
    return prev
}

                                            
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)

def reverse_list(head)
    prev = nil
    current = head
    
    while current != nil
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    end
    
    return prev
end

                                            
/**
 * Definition for singly-linked list.
 * class ListNode(var _x: Int = 0) {
 *   var next: ListNode = null
 * }
 */
object Solution {
    def reverseList(head: ListNode): ListNode = {
        var prev: ListNode = null
        var curr: ListNode = head
        while (curr != null) {
            val nextTemp = curr.next
            curr.next = prev
            prev = curr
            curr = nextTemp
        }
        prev
    }
}

                                            
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>,
// }
impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut prev = None;
        let mut current = head;
        
        while let Some(mut inner) = current {
            let next = inner.next.take();
            inner.next = prev.take();
            prev = Some(inner);
            current = next;
        }
        
        prev
    }
}

To solve this coding challenge, you will need to reverse a singly linked list either iteratively or recursively and then return the reversed list. Here's how you can approach this problem:

Explanation

In order to reverse a linked list, each node’s

next

pointer needs to point to the previous node instead of the next node, effectively reversing the direction of the list. You can achieve this by following the steps below for an iterative and a recursive solution.

Iterative Method

The iterative method involves traversing the list once and changing the direction of each node's

next

pointer:

Initialize three pointers:
prev

as
None

,
curr

as
head

(the starting node of the list), and
next_temp

to keep track of the next node in original list while reversing.
Iterate through the list. For each node:

Store the
next

node.
Reverse the
next

pointer of the current node to point to the
prev

node.
Move the
prev

pointer one step forward to the current node.
Move the
curr

pointer to the
next_temp

node.

After the loop,
prev

will be pointing to the new head of the list.
Return
prev

.

Recursive Method

The recursive method leverages the call stack to reverse the list. Here's a step-by-step explanation:

Base case: If the list is empty (
head

is
None

) or has only one node (
head.next

is
None

), simply return
head

because there's nothing to reverse.
Recursion: For the rest of the list, make a recursive call to reverse the sublist starting from the second node.
After the recursive call, reverse the
next

pointer of the second node to point back to the first node.
Set the
next

pointer of the first node to
None

to mark the end of the reversed list.
Return the new head which is the result of the recursive call.

Detailed Steps in Pseudocode

Iterative Approach

                                            
# Definition for singly-linked list node
class ListNode:
    # Node constructor initializing value and next pointer
    function init(val, next=None):
        this.val = val
        this.next = next

# Function to reverse the singly linked list iteratively
function reverseList(head):
    # Initialize previous node to None
    prev = None
    # Initialize current node to head of the list
    curr = head

    # Loop until current node is None (end of the list)
    while curr is not None:
        # Store next node temporarily
        next_temp = curr.next
        # Reverse the current node's pointer to previous node
        curr.next = prev
        # Move previous node one step forward (to current node)
        prev = curr
        # Move current node one step forward (to next_temp)
        curr = next_temp

    # At the end, prev will be the new head of the reversed list
    return prev

Recursive Approach

                                            
# Definition for singly-linked list node
class ListNode:
    # Node constructor initializing value and next pointer
    function init(val, next=None):
        this.val = val
        this.next = next

# Function to reverse the singly linked list recursively
function reverseListRecursive(head):
    # Base case: if the list is empty or has only one node, return head
    if head is None or head.next is None:
        return head

    # Recursive call to reverse the sublist starting from second node
    new_head = reverseListRecursive(head.next)

    # Reverse the next pointer of the second node to point to first node
    head.next.next = head
    # Set the next pointer of the first node to None (end of list)
    head.next = None

    # Return the new head of the reversed list
    return new_head

These pseudocode explanations provide a clear step-by-step guide to reversing a singly linked list using both iterative and recursive methods. The comments within the pseudocode make it easy to follow the logic for reversing the links within the list nodes.