题解 | #牛群的身高排序#

• 题目考察的知识点 : 链表遍历，移动，删除操作，链表排序
• 题目解答方法的文字分析：

1. 初始化dummy节点,便于头部操作令dummy.next = head。
2. 从第二个节点开始遍历链表。
3. 对于每个节点,如果其值小于前一个节点的值,则需要插入到合适位置。
4. 寻找合适的插入位置,进行节点插入操作。
5. 重复上述步骤直到链表排序完成。
6. 最终返回dummy.next。

• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def sortList(self , head: ListNode) -> ListNode:
        if not head:
            return head
    
        dummy = ListNode(0)
        dummy.next = head
    
        cur = head
        while cur and cur.next:
            if cur.val > cur.next.val:
                pre = dummy
            
                while pre.next.val < cur.next.val:
                    pre = pre.next
                
                tmp = cur.next
                cur.next = tmp.next
                tmp.next = pre.next
                pre.next = tmp
            else:
                cur = cur.next

        return dummy.next