题解 | #牛的品种排序IV#
牛的品种排序IV
https://www.nowcoder.com/practice/bd828af269cd493c86cc915389b02b9f
考察的知识点:链表的分割和合并;
解答方法分析:
- 定义两个新的链表指针
zero
和one
,分别表示值为0和值为1的节点链表的头节点。 - 初始化两个当前节点指针
curZero
和curOne
,分别指向zero
和one
的尾节点。 - 遍历原始链表,根据节点值的不同将节点放入对应的链中。具体操作如下:如果节点的值为0,将其放入值为0的链表中,更新
curZero
为当前节点。如果节点的值为1,将其放入值为1的链表中,更新curOne
为当前节点。 - 遍历结束后,将值为0的链表的尾节点指向值为1的链表的头节点,完成合并操作。
- 返回值为0的链表的头节点,即为排序后的链表。
所用编程语言:C++;
完整编程代码:↓
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* sortCowsIV(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* zero = new ListNode(0); ListNode* one = new ListNode(0); ListNode* curZero = zero; ListNode* curOne = one; while (head != nullptr) { if (head->val == 0) { curZero->next = head; head = head->next; curZero = curZero->next; curZero->next = nullptr; } else { curOne->next = head; head = head->next; curOne = curOne->next; curOne->next = nullptr; } } curZero->next = one->next; return zero->next; } };