如何实现[牛客]平台上的链表分割算法？

本文共计503个文字，预计阅读时间需要3分钟。

编写代码，以定值x为基准将链表分割成两部分。所有小于x的节点排在大于或等于x的节点之前。牛客链接+最简单思路+因为头插必然改变顺序，所以使用尾插+大于的尾插到小于的链表尾部。

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

牛客链接

最简单思路

因为头插必然改变顺序,所以使用尾插

大于的尾插到一个链表

小于的尾插到一个链表

然后链接起来

使用哨兵位的头结点,防止太多问题的产生

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode* LessTail,* LessGuardHead,* greaterGuardHead,* greaterTail; LessGuardHead = LessTail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterGuardHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterTail->next = LessTail->next = NULL; struct ListNode* cur = pHead; while(cur) { if(cur->val < x) { LessTail->next = cur; LessTail = LessTail->next; } else { greaterTail->next = cur; greaterTail = greaterTail->next; } cur = cur->next; } LessTail->next = greaterGuardHead->next; pHead = LessGuardHead->next; free(greaterGuardHead); free(LessGuardHead); return pHead; } };

内存超限一般是发生了死循环,而单链表中发生死循环,我们考虑环状链表,如下图两个链表组合后,最后一个结点还指向原来后面的结点,构成了环状链表,所以尾插后切记要置空!!

最终代码:

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode* LessTail,* LessGuardHead,* greaterGuardHead,* greaterTail; LessGuardHead = LessTail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterGuardHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterTail->next = LessTail->next = NULL; struct ListNode* cur = pHead; while(cur) { if(cur->val < x) { LessTail->next = cur; LessTail = LessTail->next; } else { greaterTail->next = cur; greaterTail = greaterTail->next; } cur = cur->next; } LessTail->next = greaterGuardHead->next; greaterTail->next = NULL;//避免环状链表 pHead = LessGuardHead->next; free(greaterGuardHead); free(LessGuardHead); return pHead; } };