Sorting Rail Cars

Function Name: sortRailCars

Description

Imagine a train sorting system where rail cars containing numbers need to be reordered according to their values. Each rail car is linked to the next, forming a chain. Your task is to write a function that receives a linked list representing a train of rail cars, and returns a linked list with the cars sorted in ascending order. You cannot use auxiliary arrays, pointers, or new data structures; the existing linked list must be manipulated to sort the cars.

Requirements

• The 'sortRailCars' function must take one parameter, which is the head of a linked list.
• Each node in the linked list has an 'intValue' representing the number on the rail car, and a 'next' reference pointing to the next car.
• The function must sort the linked list in ascending order by manipulating the nodes' 'next' references.
• Do not create any new nodes or linked lists.
• You may not use any built-in sorting methods.
• The linked list may not be converted into any other data structure for sorting.
• The function must be able to handle a linked list of at least 1,000 nodes without performance issues.
• Do not use recursion; an iterative solution is expected due to potential stack overflow concerns with large inputs.

Examples

Given a linked list: 4 -> 1 -> 3 -> 2, after calling 'sortRailCars(head)', the list should be: 1 -> 2 -> 3 -> 4.

Links