One Bubble Pass
Make a single pass from the head to the end: compare each node with the next one, and if the first is larger, swap their values. Keep going with the next pair, so a large value can travel all the way to the end. Return the head. This is one pass only, not a full sort. The list is passed in as head.
Linked lists appear in the tests as the list of their values, like [1,2,3]. Each node is a ListNode with .val and .next; the class is already defined for you.
Example 1
head [3,1,2]
returns [1,2,3]
3 and 1 swap, then 3 and 2 swap: 1, 2, 3.
Example 2
head [4,5,1,2]
returns [4,1,2,5]
4,5 stay; 5,1 swap; 5,2 swap: 4, 1, 2, 5.
Constraints
0 <= number of nodes <= 100-100 <= Node.val <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Linked lists problems
- Running Totals ListBeginner
- Second Largest ValueBeginner
- Sum of the First KBeginner
- Sum of the ValuesBeginner
- Swap First and Last ValuesBeginner
- Values in Reverse OrderBeginner
- Add Lists Position by PositionEasy
- Append a ValueEasy