Reverse both parts

Summary

Given a linked list, reverse the first half and then the second half. This problem involves understanding how to manipulate a linked list and reversing it.

Detailed Explanation

To solve this problem, we'll divide the linked list into two halves - the first half and the second half. Then, we'll reverse each of these halves separately.

Here's a step-by-step breakdown:

Find the middle of the linked list: Traverse the linked list until you reach its middle. This can be done by counting the number of nodes or using a fast-slow pointer approach.
Reverse the first half: Traverse the linked list from the head to the middle node, reversing each node as you go. You'll need to update the next pointers accordingly.
Reverse the second half: Traverse the linked list from the middle node to the end, reversing each node as you go. Again, update the next pointers correctly.
Combine the two reversed halves: Set the new head of the reversed linked list to be the first node of the reversed first half. The rest of the nodes will follow in reverse order.

Time complexity: O(n), where n is the number of nodes in the linked list. This is because we're traversing the linked list twice. Space complexity: O(1), as we're only using a constant amount of space to store our pointers and variables.

Optimized Solutions

Java

public class LinkedList { public Node reverseBothParts(Node head) { if (head == null || head.next == null) return head; // Find the middle node Node slow = head; Node fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } // Reverse the first half Node prev = null; Node curr = head; while (curr != slow) { Node nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } // Reverse the second half prev = null; curr = slow; while (curr.next != null) { Node nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } // Combine the two reversed halves head = prev; return head; } }