Reverse a Singly Linked list

Iterative solution: A singly linked list can be reversed in Java by iterating through the list and updating the next pointers of each node. Here is an example of a Java method that reverses a singly linked list:

public static Node reverseList(Node head) {
    Node prev = null;
    Node current = head;
    while (current != null) {
        Node next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

In the above code, the reverseList method takes the head of the linked list as input. It initializes a prev variable to null and a current variable to the head of the list. It then enters a loop that continues as long as current is not null. Inside the loop, it creates a new variable next that holds the current node's next pointer. It then updates the current node's next pointer to prev. After that, it shifts the prev pointer to the current node and the current pointer to the next node. At the end of the loop, the method returns the prev pointer which now points to the last node of the original linked list and it becomes the head of the reversed linked list.

It’s important to note that this approach modifies the original linked list and it doesn’t require any additional memory, as it uses the nodes of the original list to build the reversed list.

In summary, reversing a singly linked list in Java can be achieved by iterating through the list and updating the next pointers of each node, keeping track of the previous and current node, and finally returns the last node of the original list which now becomes the head of the reversed list.=

Recursive Solution: A singly linked list can also be reversed in Java recursively by following these steps:

Base case: If the head of the list is null or if it is the last node of the list, it should be returned as it is.

Recursive case: If the head of the list is not null, call the reverseList method recursively for the next node.

Change the next pointer of the head of the list to null, as it will become the last node of the reversed list. Connect the head of the original list to the tail of the reversed sub-list. Here is an example of a Java method that reverses a singly linked list recursively:

public static Node reverseList(Node head) {
  if (head == null || head.next == null) {
    return head;
  }
  Node reversedTail = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return reversedTail;
}

The above code, the reverseList method takes the head of the linked list as input. It first checks if the head of the list is null or if it is the last node of the list, it should be returned as it is. If the head of the list is not null, it calls the reverseList method recursively for the next node and assigns the returned value to reversedTail. Then it updates the next pointer of the next node to point to the head of the original list, and the next pointer of the head is set to null. Finally, the method returns the reversedTail, which is the new head of the reversed list.

As with the previous example, this approach modifies the original linked list and it doesn’t require any additional memory, as it uses the nodes of the original list to build the reversed list.

In summary, reversing a singly linked list in Java recursively can be achieved by following the base case and recursive case, changing the next pointer of the head of the list to null, and connecting the head of the original list to the tail of the reversed sub-list.