程序员面试金典-0204-分割链表

绝地灬酷狼 2022-11-08 15:28 111阅读 0赞

## 程序员面试金典-0204-分割链表 ##

本题可以看作是链表的插入操作练习

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。
    
    示例:
    
    输入: head = 3->5->8->5->10->2->1, x = 5
    输出: 3->1->2->10->5->5->8
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/partition-list-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    struct ListNode* partition(struct ListNode* head, int x){
        
        int len = 0;
        int i = 0;
    
        struct ListNode * p = head;
        while(p!=NULL){
        
            len++;
            p=p->next;
        }
    
        struct ListNode * temp_head = malloc(sizeof(struct ListNode));
        temp_head -> val = -1;
        temp_head -> next = NULL;
    
        p = head;
        while(i<len){
        
            int temp_val = p -> val;
            if(temp_val >= x){
        
                struct ListNode * t = temp_head;
                while(t->next != NULL){
        
                    t = t->next;
                }
                struct ListNode * rear = malloc(sizeof(struct ListNode));
                rear->val = temp_val;
                rear->next = NULL;
                t->next = rear;
            }
            else{
        
                struct ListNode * head = malloc(sizeof(struct ListNode));
                head->val = temp_val;
                head->next = temp_head->next;
                temp_head->next = head;
            }
            i++;
            p = p->next;
        } 
        struct ListNode * ret = temp_head->next;
        free(temp_head);
        return ret;
    }