单链表算法 - 链表分割

链表分割_牛客题霸_牛客网现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的。题目来自【牛客题霸】https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70思路:

代码:

/*
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//创建两个非空链表:小链表和大链表ListNode* lesstHead,*lesstTail;lesstHead = lesstTail = (ListNode*)malloc(sizeof(ListNode));ListNode* greaterHead,*greaterTail;greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//创建临时变量来遍历原数组ListNode* prev = pHead;while(prev){//判断当前节点是否小于xif(prev->val < x){//插入到小链表中lesstTail->next = prev;lesstTail = lesstTail->next;}else{//插入到大链表中greaterTail->next = prev;greaterTail = greaterTail->next;}prev = prev->next;}//退出循环原链表遍历完成//连接两个链表lesstTail->next = greaterHead->next;ListNode* ret = lesstHead->next;free(lesstHead);lesstHead = NULL;free(greaterHead);greaterHead = NULL;return ret;}
};

提交结果:

当我们提交代码之后代码有问题,那么代码到底哪里的逻辑不合适呢?我们画图看一下。

/*
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//创建两个非空链表:小链表和大链表ListNode* lesstHead,*lesstTail;lesstHead = lesstTail = (ListNode*)malloc(sizeof(ListNode));ListNode* greaterHead,*greaterTail;greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//创建临时变量来遍历原数组ListNode* prev = pHead;while(prev){//判断当前节点是否小于xif(prev->val < x){//插入到小链表中lesstTail->next = prev;lesstTail = lesstTail->next;}else{//插入到大链表中greaterTail->next = prev;greaterTail = greaterTail->next;}prev = prev->next;}//将大链表的尾节点的next指针置为NULLgreaterTail->next = NULL;//连接两个链表lesstTail->next = greaterHead->next;ListNode* ret = lesstHead->next;free(lesstHead);lesstHead = NULL;free(greaterHead);greaterHead = NULL;return ret;}
};

提交结果: