做剧情游戏的网站,wordpress展览会,在线网页代理服务器,wordpress创建相册一、题目 函数原型#xff1a; ListNode* partition(ListNode* pHead, int x) 二、思路 根据题意#xff0c;可以设置两个新的链表#xff0c;将原链表中所有小于x的结点链接到链表1中#xff0c;大于x的结点链接到链表2中#xff0c;最后再将两个链表合并即可。 此题有两… 一、题目 函数原型 ListNode* partition(ListNode* pHead, int x) 二、思路 根据题意可以设置两个新的链表将原链表中所有小于x的结点链接到链表1中大于x的结点链接到链表2中最后再将两个链表合并即可。 此题有两种写法一种是带哨兵位的链表另一种是不带哨兵位的链表。 实际操作过程中发现对于两个链表的合并带哨兵位链表比不带哨兵位链表的代码更加简洁。 带哨兵位的结点进行尾插时不需要考虑头结点是否为空且链表合并时可以直接合并无需考虑某一链表是否为空的情况 三、代码 代码实现1带哨兵位 /*
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 hereListNode *Bnewhead(ListNode*)malloc(sizeof(ListNode));//小链表的哨兵位ListNode *BtailBnewhead;//大链表尾指针ListNode *Snewhead(ListNode*)malloc(sizeof(ListNode));//大链表的哨兵位ListNode *StailSnewhead;//小链表尾指针ListNode *curpHead;//遍历指针while(cur){if(cur-valx)//结点值小于x尾插到小链表{Stail-nextcur;Stailcur;}else//结点大于x尾插到大链表{Btail-nextcur;Btailcur;}curcur-next;}Stail-nextNULL;//小链表尾结点指针域指向空Btail-nextNULL;//大链表尾结点指针域指向空Stail-nextBnewhead-next;//将大小链表合并return Snewhead-next;//返回新链表的头结点非哨兵位}
}; 代码实现2不带哨兵位 /*
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 hereListNode *curpHead;ListNode *BnewheadNULL;//大链表头结点ListNode *BtailNULL;//大链表尾指针ListNode *SnewheadNULL;//小链表头结点ListNode *StailNULL;//小链表尾指针while(cur)//遍历原链表{if(cur-valx)//结点值小于x尾插到小链表{if(StailNULL)//先判断小链表是否为空为空则将插入结点作为头结点{SnewheadStailcur;}else//小链表不为空进行尾插{Stail-nextcur;Stailcur;}}else{if(BtailNULL)//先判断大链表是否为空为空则将插入结点作为头结点{BnewheadBtailcur;}else//大链表不为空进行尾插{Btail-nextcur;Btailcur;}}curcur-next;}if(Btail)//将大链表尾结点指针域指向空Btail-nextNULL;if(Stail)//将小链表尾结点指针域指向空Stail-nextNULL;//开始合并大小链表if(StailNULL)//如果小链表为空则直接返回大链表{return Bnewhead;}else if(BtailNULL)//如果大链表为空则直接返回小链表{return Snewhead;}else if(StailNULLBtailNULL)//如果大小链表都为空则直接返回空{return NULL;}else//大小链表都不为空将两个链表合并{Stail-nextBnewhead;return Snewhead;} }
};
