考察的知识点:与链表有关的题基本都是插入,删除,交换顺序等,解决这些问题通常将链表的指针进行修改。
问题分析:要将单链表按照大小重新排序,使大的在一边,小的在一边,所以定义两个头结点,遍历单链表,一个头结点连接大的结点,另一个头结点连接小的结点,然后再进行合并,给nullptr的给nullptr即可。
本题解析所用的编程语言:c++
ListNode* cow_partition(ListNode* head, int x) { // write code here ListNode* headsmall = new ListNode(-1); ListNode* headgreat = new ListNode(-1); ListNode* cur = head, * cur1 = headsmall, * cur2 = headgreat; while (cur) { if (cur->val < x) //小的插入到headsmall { cur1->next = cur; cur1 = cur1->next; } else //大的插入到headgreat { cur2->next = cur; cur2 = cur2->next; } cur = cur->next; } //将两个链表合并 cur1->next = headgreat->next; cur2->next = nullptr; head = headsmall->next; //删除 delete headsmall; delete headgreat; return head; }