《程序员面试金典》链表分割

题目链接：?rp=1&ru=/ta/cracking-the-coding-interview&qru=/ta/cracking-the-coding-interview/question-ranking

题目描述编写代码，以给定值x为基准将链表分割成两部分，，所有小于x的结点排在大于或等于x的结点之前给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。思路我们可以开两个新的链表，一个small保存比x小的结点，一个big保存大于等于x的结点，最后再将两个节点拼接起来即可

/*struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}};*/class Partition{public:ListNode* partition(ListNode* pHead, int x){// write code hereif(pHead==nullptr)return nullptr;ListNode *pNode = pHead;ListNode *small = new ListNode(0);ListNode *big = new ListNode(0);ListNode *ptr1 = small;ListNode *ptr2 = big;while(pNode){if(pNode->val<x){ptr1->next = pNode;pNode = pNode->next;ptr1 = ptr1->next;ptr1->next = nullptr;}else{ptr2->next = pNode;pNode = pNode->next;ptr2 = ptr2->next;ptr2->next = nullptr;}}ptr1->next = big->next;return small->next;}};

也不要说曾经失去，失去的不是永远失去，得到的不是永远拥有，

相关文章：

你感兴趣的文章：

标签云：