Question: You are given a singly linked list. Reorder the list such that the first element points to the last element, the second element points to the second last element, and so on. You should modify the original linked list and not create a new one. For example, given the linked list 1->2->3->4->5, you should modify it to 1->5->2->4->3.
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def reorderList(head):
if not head or not head.next:
return
# Step 1: Find the middle of the linked list using fast and slow pointer approach
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Step 2: Reverse the second half of the linked list
prev = None
current = slow.next
while current:
temp = current.next
current.next = prev
prev = current
current = temp
slow.next = None
# Step 3: Merge the two halves of the linked list
p1 = head
p2 = prev
while p1 and p2:
temp1 = p1.next
temp2 = p2.next
p1.next = p2
p2.next = temp1
p1 = temp1
p2 = temp2
# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reorderList(head)
# The linked list will be reordered to 1->5->2->4->3
In this approach, we first find the middle of the linked list using the fast and slow pointer approach. Then we reverse the second half of the list. Finally, we merge the two halves by alternating the nodes to reorder the linked list.