分隔链表

NC23 划分链表 同款题目？

typedef struct ListNode ListNode;

struct ListNode* partition(struct ListNode* head, int x){
    if(head == NULL)  // 如果传入的链表是空链表
        return NULL;

    ListNode* lessHead = (ListNode*)malloc(sizeof(ListNode));  // 哨兵位
    ListNode* lessTail = lessHead;
    lessTail->next = NULL;
    ListNode* greaterHead = (ListNode*)malloc(sizeof(ListNode));  // 哨兵位
    ListNode* greaterTail = greaterHead;
    greaterTail->next = NULL;

    ListNode* cur = head;
    while(cur)
    {
        printf("cur->val=%d\n", cur->val);
        if(cur->val < x)  // 找小于x的节点
        {
            lessTail->next = cur;
            lessTail = lessTail->next;
            printf("lessTail->val=%d\n", lessTail->val);
        }
        else  // 找大于或等于x的节点
        {
            greaterTail->next = cur;
            greaterTail = greaterTail->next;
            printf("greaterTail->val=%d\n", greaterTail->val);
        }

        cur = cur->next;
    }

    lessTail->next = greaterHead->next;  // 对两个链表进行拼接
    greaterTail->next = NULL;  // 置空，防止新链表出现环
    ListNode* list = lessHead->next;  // list是新链表真正意义上的头节点
    free(greaterHead);  // 释放哨兵位
    free(lessHead);  // 释放哨兵位

    return list; 
}

    def partition(self , head: ListNode, x: int) -> ListNode:
        dummy,p1 = ListNode(0),head
        dummy.next = head
        p1pre = dummy
        '''step1 找到目标分界节点，及其前一个节点'''
        while p1!=None and p1.val<x:
            p1pre = p1
            p1 = p1.next
        '''step 2 从目标分界节点 p1 往后遍历检查，值<x的节点就往 prep1,p1中 间***r />         p2pre,p2 = p1pre,p1
        while p2!=None:
            if p2.val<x: 
                p2pre.next = p2.next #断尾
                p2.next = p1 #插到前边
                p1pre.next = p2
                p1pre = p2 #指针重置给下一轮
                p2 = p2pre.next
            else:
                p2pre = p2
                p2 = p2.next
        return dummy.next