题解 | #牛群的身高排序# java
牛群的身高排序
https://www.nowcoder.com/practice/9ce3d60e478744c09768d1aa256bfdb5
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode sortList (ListNode head) {
// write code here
if (head == null || head.next == null) {
return head; // 如果链表为空或只有一个节点，则无需排序，直接返回
}
boolean swapped; // 用于标记是否进行了交换操作
ListNode current;
ListNode previous = null;
do {
swapped = false;
current = head;
while (current.next != previous) { // 遍历链表节点
if (current.val >
current.next.val) { // 如果当前节点的值大于下一个节点的值，则交换它们
int temp = current.val;
current.val = current.next.val;
current.next.val = temp;
swapped = true; // 更新交换标记
}
current = current.next; // 继续遍历下一个节点
}
previous =
current; // 参与排序的最后一个节点已经是有序的，不再重复比较，更新previous指针
} while (swapped); // 如果进行了交换操作，则需要继续进行排序
return head;
}
}
题目主要考察以下知识点：
- 链表的基本操作：如何定义链表节点、如何构建一个链表，以及如何遍历链表。
- 排序算法：这里使用了冒泡排序算法对链表进行排序。冒泡排序是一种简单直观的排序算法，通过不断比较相邻元素并交换位置来达到排序的目的。
- 指针操作：在链表排序过程中，需要使用指针来访问、操作链表节点，包括指向当前节点和下一个节点的指针。
代码解释：
- 定义链表节点类ListNode，包含一个整数val和一个指向下一个节点的指针next。
- 编写排序方法sortList，接收链表的头结点head作为输入参数，并返回排序后的链表头结点。
- 在sortList方法中，首先判断链表是否为空或只有一个节点，如果是则直接返回原链表。
- 使用一个布尔变量swapped来标记是否进行了交换操作，初始化为false。
- 创建两个指针current和previous，current用于遍历链表节点，previous用于记录上一轮排序的最后一个节点。
- 使用do-while循环，在每次循环中进行一轮冒泡排序操作。
- 在循环中，将current指针重新指向链表头结点，开始遍历链表节点。
- 如果当前节点current的值大于下一个节点的值，则交换它们的值，并将swapped标记为true。
- 遍历完一轮后，更新previous指针为当前节点current，意味着参与排序的最后一个节点已经是有序的，不再重复比较。
- 如果进行了交换操作（即swapped为true），则需要继续进行排序，否则排序完成。
- 返回排序后的链表头结点head。
- 在main方法中构建示例链表，调用sortList方法对链表进行排序。
- 遍历排序后的链表，输出每个节点的值。
