现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
如果不要求保持相对顺序不变,那么小于x的结点头插,大于x的结点尾插。但是要求保持相对顺序不变,这种方法就不适用。
创建两个新链表,一个存放小于x的结点,一个存放大于x的结点,然后将两个链表链接起来。
创建两个带哨兵位的头结点
这里要注意,在原链表中,结点7的下一个结点是3,所以这里必须将结点7的next置为NULL,否则结点7的next是结点3,这样就造成死循环。
struct ListNode {
int val;
struct ListNode* next;
};
struct ListNode* partition(struct ListNode* pHead, int x)
{
struct ListNode* lessHead = NULL;
struct ListNode* lessTail = NULL;
struct ListNode* greatHead = NULL;
struct ListNode* greatTail = NULL;
//带哨兵位头结点,方便尾插
lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
greatHead = greatTail = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = pHead;
while (cur != NULL)
{
if (cur->val >= x)
{
//尾插到great中
greatTail->next = cur;
greatTail = cur;
}
else
{
//尾插到less中
lessTail->next = cur;
lessTail = cur;
}
cur = cur->next;
}
//两个链表链接起来
lessTail->next = greatHead->next;
greatTail->next = NULL;
//记住新链表的表头
struct ListNode* head = lessHead->next;
//释放空间
free(lessHead);
free(greatHead);
return head;
}
OJ错误:内存超出限制,程序可能出现死循环等问题。这里注意,若不将greatTail->next = NULL,就会报内存超出限制。
文章评论