题解 | #链表分割#

链表分割

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
       ListNode* less, *greater, *cur = pHead;
       //创建两个哨兵节点
       less = (ListNode*)malloc(sizeof(ListNode));
       greater = (ListNode*)malloc(sizeof(ListNode));
       //用small,bigger分别保留哨兵节点
       ListNode* small = less, *bigger = greater;
       while(cur)
       {
        if(cur->val < x)
        {
            less->next = cur;
            less = less->next;         
        }
        else
        {
            greater->next = cur;
            greater = greater->next;           
        }
        cur = cur->next;
       }
       //进行拼接
       greater->next = NULL;//防止环形
       less->next = bigger->next;//链接
       pHead = small->next;//要返回的头结点
       free(small);
       free(bigger);
       return pHead;    
    }
};

全部评论

相关推荐

下北澤大天使:你是我见过最美的牛客女孩😍
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务