328. Sort Linked List Using Bubble Sort

Given the head of a singly linked list, sort it in ascending order using the bubble sort algorithm by swapping node values (not pointers). Return the head of the sorted list.

Bubble sort: repeatedly compare adjacent nodes and swap their values if out of order.

Input: Head of a singly linked list.

Output: Head of the sorted linked list (ascending).

Examples

Input: [4,2,1,3]
Output: [1,2,3,4]
Explanation: Pass1: [2,1,3,4]→[1,2,3,4]. No more swaps. Sorted.

Input: [5,1,3,2,4]
Output: [1,2,3,4,5]
Explanation: Multiple bubble passes until sorted.

Input: [1]
Output: [1]
Explanation: Single node. Already sorted.

Constraints

• 1<=nodes<=10^4
• -10^4<=Node.val<=10^4

Asked by