LeetCode 面试题02.04.分割链表
LeetCode 面试题02.04.分割链表 C写法
思路🤔:
将x分为两段,一段放小于x的值,另一段放大于x的值。开辟四个指针lesshead、lesstail、greaterhead、greatertail,head为哨兵位,防止链表为空时情况过于复杂,tail为尾结点,将链表的值进行大小判断后尾插完成分段,分段后再链接,最后释放哨兵位完成整个链表的分割。
代码:
struct ListNode* partition(struct ListNode* head, int x){ struct ListNode* lesshead,*lesstail,*greaterhead,*greatertail; lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode)); lesstail->next = greatertail->next = NULL; //将链表分为两段存储 struct ListNode* cur = head; while(cur) { if(cur->val next = cur; lesstail = lesstail->next; } else { greatertail->next = cur; greatertail = greatertail->next; } cur = cur->next; } lesstail->next = greaterhead->next; //链接两段链表,哨兵位不放数据所以要链接到next greatertail->next = NULL; //单链表最后要指向空 struct ListNode* list = lesshead->next; //完整链表 free(greaterhead); free(lesshead); return list; }
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。