LeetCode 面试题02.04.分割链表

07-14 1468阅读

LeetCode 面试题02.04.分割链表 C写法

LeetCode 面试题02.04.分割链表

思路🤔:

​ 将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;
}

LeetCode 面试题02.04.分割链表

VPS购买请点击我

文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。

目录[+]