题解 | #牛的品种排序IV#

• 题目考察的知识点 : 链表排序
• 题目解答方法的文字分析：

1. 由于题目要求的链表比较特殊，只有0和1两种值，所以我们可以通过计数的方式还原排序后的链表
2. 统计0和1的数量
3. 构建一个空链表dummy，先填充0的数量个0节点，再填充1的数量个1节点
4. 返回dummy.next

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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def sortCowsIV(self , head: ListNode) -> ListNode:
        zeroCount = 0
        oneCount = 0

        ptr = head 
        while ptr:
            if ptr.val == 0:
                zeroCount += 1
            else:
                oneCount += 1
            ptr = ptr.next

        dummy = ListNode(0)
        cur = dummy

        for _ in range(zeroCount):
            cur.next = ListNode(0)
            cur = cur.next
  
        for _ in range(oneCount):
            cur.next = ListNode(1)
            cur = cur.next

        return dummy.next