您现在的位置是:首页 >其他 >单链表OJ题:LeetCode--面试题:02.04 分割链表网站首页其他
单链表OJ题:LeetCode--面试题:02.04 分割链表
朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode面试题:02.04.分割链表
LeetCode :LeetCode刷题训练营
LeetCode面试题:02.04.分割链表https://leetcode.cn/problems/partition-list-lcci/
目录
1.题目介绍
LeetCode:
给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
牛客网:
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
两个题目描述都差不多,但是牛客网要求不能改变相对位置,LeetCode则不在乎相对位置,那么我们就不改变相对位置了。
2.实例演示
3.解题思路
链表的分割有两种方法:
1.不带哨兵位的头结点
2.带哨兵位的头结点
(两种方法都比较简单,但是带哨兵位的话会稍微的方便一点,这里考虑到有的老铁不知道哨兵位,因此我们两种方法都来演示一下)
3.1不带哨兵位的头结点
不带哨兵位就是直接尾插法:创建两个新的链表,遍历原链表,将小于x的结点尾插到第一个链表head1中,将大于等于x的结点尾插到head2中,尾插结束后将tail2指向的next置为NULL,与原链表断开,然后将head2链接在head1的后面,这里要考虑特殊情况:
1.两个链表第一次尾插时需要注意空指针的问题。
2.在遍历完原链表之后,如果head1为空时可以直接返回head2,如果head2为空,可以直接返回head1。
3.好多老铁好奇为什么不把tail1的next也置为空,这里可以置为空也可以不置为空,因为在下面链接的时候会改变tail1的next。
LeetCode - 代码演示(C语言实现):
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* partition(struct ListNode* head, int x){ //创建两个新的链表 struct ListNode* head1 = NULL; struct ListNode* tail1 = NULL; struct ListNode* head2 = NULL; struct ListNode* tail2 = NULL; struct ListNode* cur = head; //遍历 while(cur) { //小于x的插入第一个链表 if(cur->val < x) { //第一次尾插 if(tail1 == NULL) { head1 = tail1 = cur; } else { tail1->next = cur; tail1 = tail1->next; } } //大于或等于x的插入第二个链表 else { if(tail2 == NULL) { head2 = tail2 = cur; } else { tail2->next = cur; tail2 = tail2->next; } } //迭代 cur = cur->next; } //断开与原链表的联系 if(tail2 != NULL) { tail2->next = NULL; } //判断特殊情况 if(head1 == NULL) { return head2; } if(head2 == NULL) { return head1; } //链接第一个链表和第二个链表 tail1->next = head2; return head1; }
牛客网 - 代码实现(C++实现):
/* 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* head1 = NULL; ListNode* tail1 = NULL; ListNode* head2 = NULL; ListNode* tail2 = NULL; ListNode* cur = pHead; //遍历 while(cur) { //小于x的插入第一个链表 if(cur->val < x) { //第一次尾插 if(tail1 == NULL) { head1 = tail1 = cur; } else { tail1->next = cur; tail1 = tail1->next; } } //大于或等于x的插入第二个链表 else { if(tail2 == NULL) { head2 = tail2 = cur; } else { tail2->next = cur; tail2 = tail2->next; } } //迭代 cur = cur->next; } //断开与原链表的联系 if(tail2 != NULL) { tail2->next = NULL; } //判断特殊情况 if(head1 == NULL) { return head2; } if(head2 == NULL) { return head1; } //链接第一个链表和第二个链表 tail1->next = head2; return head1; } };
3.2带哨兵位的头结点
带哨兵位的头结点相比较于不带哨兵位的头结点的方法就略显简便,不需要考虑太多的NULL指针的问题,我们依旧采用的是直接尾插法:创建两个新的链表,遍历原链表,将小于x的结点尾插到第一个链表head1中,将大于等于x的结点尾插到head2中,尾插结束后将head2指向的next置为NULL,与原链表断开,然后将head2链接在head1的后面,这里就不需要考虑空指针的问题,直接尾插,尾插结束之后,不能直接将head2链接在tail1的后面,需要将head2的next链接,注意:哨兵位的头节点是动态开辟的,所以要释放掉,因此还要将链接之后的链表再链接在原链表的头上面,释放掉两个有哨兵位的链表:
LeetCode - 代码演示(C语言实现):
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* partition(struct ListNode* head, int x){ struct ListNode* head1, *tail1, *head2, *tail2; //创建带哨兵位的头结点 head1 = tail1 = (struct ListNode*)malloc(sizeof(struct ListNode)); head2 = tail2 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur = head; while(cur) { //小的链接在第一个链表 if(cur->val < x) { tail1->next = cur; tail1 = tail1->next; } else { tail2->next = cur; tail2 = tail2->next; } //迭代 cur = cur->next; } //断开与原链表的联系 tail2->next = NULL; //链接两个新的链表 tail1->next = head2->next; //将新链表链接在原来的头结点上面 head = head1->next; //释放 free(head1); free(head2); return head; }
牛客网 - 代码实现(C++实现):
/* 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* head1, *tail1, *head2, *tail2; //创建带哨兵位的头结点 head1 = tail1 = (ListNode*)malloc(sizeof(ListNode)); head2 = tail2 = (ListNode*)malloc(sizeof(ListNode)); struct ListNode* cur = pHead; while(cur) { //小的链接在第一个链表 if(cur->val < x) { tail1->next = cur; tail1 = tail1->next; } else { tail2->next = cur; tail2 = tail2->next; } //迭代 cur = cur->next; } //断开与原链表的联系 tail2->next = NULL; //链接两个新的链表 tail1->next = head2->next; //将新链表链接在原来的头结点上面 pHead = head1->next; //释放 free(head1); free(head2); return pHead; } };
今天的博客就分享到这里,喜欢的老铁留下你的三连,感谢感谢!我们下期再见!!