邯郸做网站的地方,合肥到黄山旅游攻略,青州做网站的电话,合肥建设监理协会网站题目一#xff1a; 题目链接#xff1a;
思路一#xff1a;使用带头链表 1.构建两个新的带头链表#xff0c;头节点不存储数据。 2.循环遍历原来的链表。 3.小于x的尾插到第一个链表。 4.大于等于x尾插到第二个链表。 5.进行链表合并#xff0c;注意第二个链表的尾的下一…题目一 题目链接
思路一使用带头链表 1.构建两个新的带头链表头节点不存储数据。 2.循环遍历原来的链表。 3.小于x的尾插到第一个链表。 4.大于等于x尾插到第二个链表。 5.进行链表合并注意第二个链表的尾的下一个需要置空防止成环。 6.free两个头之前需要保存新的满足条件的单链表的头。 #include cstddef
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* curpHead;//使用头节点先开辟一个节点struct ListNode* lefthead,*lefttile;struct ListNode* righthead,*righttile;leftheadlefttile(ListNode*)malloc(sizeof(ListNode));rightheadrighttile(ListNode*)malloc(sizeof(ListNode));//遍历链表分到左右两个链表里面while(cur){ListNode* nextcur-next;//比cur小于等于if(cur-valx){lefttile-nextcur;lefttilelefttile-next;}else {righttile-nextcur;righttilerighttile-next;}curnext;}//进行连接,有可能成环所以比x大的链表部分结尾需要置空。lefttile-nextrighthead-next;righttile-nextNULL;struct ListNode* headlefthead-next;//tile不可以释放free(lefthead),free(righthead);return head;}
};思路二使用单链表 1.有一些地方需要更改。 2.两个链表都有数据链表初始化头和尾是需要判断的。 3.两个链表都有数据那么跟上一个在链接上是差不多的。 4.当其中一个链表没有数据的时候返回另一个链表的第一个。 class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code here//不开辟头节点struct ListNode* leftfirstNULL,*lefttileNULL;struct ListNode* rightfirstNULL,*righttileNULL;//struct ListNode* curpHead;//不存在头节点是需要判断的。while(cur){struct ListNode* nextcur-next;if(cur-valx){if(leftfirstNULL){leftfirstlefttilecur;}else{lefttile-nextcur;lefttilelefttile-next;}}else{if(rightfirstNULL){rightfirstrighttilecur;}else{righttile-nextcur;righttilerighttile-next;}}curnext;}if(lefttileNULL){return rightfirst;}if(righttileNULL){return leftfirst;}lefttile-nextrightfirst;righttile-nextNULL; return leftfirst;}
};
