leetcode 链接：分割链表

题目

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

示例：

  1. 输入: head = 3->5->8->5->10->2->1, x = 5
  2. 输出: 3->1->2->10->5->5->8
  3. 注意：输出答案不唯一，只要3、1、2这几个比5小的数字排在最前面即可（这三个数字的顺序也不要求）

解答 & 代码

  • 设定一个虚拟头节点 dummyHead
  • 遍历链表节点，假设当前遍历的节点为 cur
    • 如果 cur 节点的值小于分割基准 x 的值，并且 cur 的前驱节点不是虚拟头节点 dummyHead ，则把 cur 节点移动到虚拟头节点 dummyHead 后面
      • 注意： cur 的前驱节点不是虚拟头节点 dummyHead 时，才需要移动，否则移动了是白忙活，因为 cur 节点本来就在虚拟头节点 dummyHead 后面，而且在执行移动的代码时会遇到问题，即执行完下面代码后，pre 所指示的节点不对：

image.png

  • 否则，继续遍历下一个节点

    /**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
   ListNode* dummyHead = new ListNode(0);
   dummyHead->next = head;

   // 遍历链表节点，将小于 x 的节点移到虚拟头部后面
   ListNode* cur = dummyHead->next;
   ListNode* pre = dummyHead;
   while(cur != NULL)
   {
       if(cur->val < x && pre != dummyHead)
       {
           pre->next = cur->next;

           cur->next = dummyHead->next;
           dummyHead->next = cur;

           cur = pre->next;
       }
       else
       {
           pre = cur;
           cur = cur->next;
       }
   }

   return dummyHead->next;
}
};

    执行结果： ``` 执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 94.16% 的用户 内存消耗：9.9 MB, 在所有 C++ 提交中击败了 50.72% 的用户 ```