链表分割如何改写为长尾词？

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

编写代码，将链表分割为两部分，其中包含所有大于或等于x的节点在前，小于x的节点在后。思路如下：

牛客链接 + 简单思路 + 因为首部插入必然改变顺序，所以使用尾插 + 将大于x的节点插入到一个新的链表，从大于x的尾节点开始到大于等于x的尾节点，然后将小于x的链表链接到这个链表之后。

pythonclass ListNode: def __init__(self, val=0, next=None): self.val=val self.next=next

def partition(head, x): dummy1=ListNode(0) dummy2=ListNode(0) prev1=dummy1 prev2=dummy2 cur=head

while cur: if cur.val >=x: prev1.next=cur prev1=cur else: prev2.next=cur prev2=cur cur=cur.next

prev2.next=None prev1.next=dummy2.next

return dummy1.next

编写代码，以给定值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; } };