leetcode做题笔记86分隔链表

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

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

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

思路一：创建新链表进行修改

struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode*p1Head=(struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode*p2Head=(struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode*p1=p1Head;
    struct ListNode*p2=p2Head;
    struct ListNode*p=head;

    while(p){
        if(p->val<x){
            p1->next=p;
            p1=p;
        }
        else{
            p2->next=p;
            p2=p;
        }
        p=p->next;
    }
  p2->next=NULL;
    p1->next=p2Head->next;
    return p1Head->next;

}

分析：

本题将小于x的节点全部放在前面，可新建两个个链表，一个存储小于x的节点，一个储存大于等于x的节点，然后连接两个链表再返回新链表

思路二：原地修改


struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* slow = &dummy;
    while(slow->next != NULL && slow->next->val<x){
        slow = slow->next;
    }
    struct ListNode* fast = slow;

    while(fast && fast->next){
        if(fast->next->val < x){
            struct ListNode* tmp = fast->next;
            fast->next = tmp->next;
            tmp->next = slow->next;
            slow->next = tmp;
            slow = slow->next;
        }
        else
        fast = fast->next;
    }

    return dummy.next;
}