LeetCode：86. Partition List分隔链表(C语言)

淡淡的烟草味﹌ 2023-01-01 13:57 66阅读 0赞

**题目描述：**  
给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例：

输入：head = 1->4->3->2->5->2, x = 3  
输出：1->2->2->4->3->5

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/partition-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
    
    
    struct ListNode* partition(struct ListNode* head, int x){ 
        struct ListNode *ListLess = NULL;
        struct ListNode *ListGreater = NULL;
    
        struct ListNode *h1 = NULL;
        struct ListNode *h2 = NULL;
    
        struct ListNode *p = head;
    
        while(p){ 
            if(p->val < x){ 
                if(NULL == ListLess){ 
                    ListLess = p;       //首次找到小于x的节点后，ListLess指向p
                    h1 = ListLess;      //h1指向ListLess
                }
                else{ 
                    ListLess->next = p; //非首次找到小于x的节点后，ListLess->next指向p节点
                    ListLess = p;       //非首次找到小于x的节点后，将ListLess重新指向p
                }
            }
            else{ 
                if(NULL == ListGreater){ 
                    ListGreater = p;    //首次找到大于x的节点后，ListGreater指向p
                    h2 = ListGreater;   ///h2指向ListGreater
                }
                else{ 
                    ListGreater->next = p;  //非首次找到大于x的节点后，ListGreater->next指向p节点
                    ListGreater = p;        //非首次找到大于x的节点后，将ListGreater重新指向p
                }
            }
    
            p = p->next;                    //p指向p->next
        }
    
        if(NULL == ListLess){ 
            return h2;                      //若ListLess为空返回h2
        }
        if(NULL == ListGreater){ 
            return h1;                      //若ListGreater为空返回h1
        }
    
        //将ListLess以及ListGreater拼接返回
        ListGreater->next = NULL;           
        ListLess->next = h2;
    
        return h1;
    }

**运行结果：**  
![在这里插入图片描述][20210103105040937.png_pic_center]

[20210103105040937.png_pic_center]: /images/20221120/4f2dc5ebe6c040c081f20a60c1ec5440.png