编写一个程序将单链表按基准划分

为两部分，比基准小的节点在前面，大于等于基准的节点在后面。可以使用额外的空间，要求算法时间复杂度为O(n)。

好的，您的问题是如何将单链表按基准划分为两部分，比基准小的节点在前面，大于等于基准的节点在后面。算法时间复杂度为O(n)，可以使用额外的空间。

以下是一个可能的解决方案：

建立两个新的链表，分别为small和big。遍历原始链表，将小于基准的节点加入small链表，将大于等于基准的节点加入big链表。最后将small链表的尾部指向big链表的头部，即可得到新的链表。同时，还需要保持原始链表的顺序不变。时间复杂度为O(n)，需要额外的空间来存储两个新链表。

以下是代码实现的示例：

struct LinkedListNode {
  int value;
  LinkedListNode* next;
};

LinkedListNode* partitionLinkedList(LinkedListNode* head, int pivot) {
  LinkedListNode* smallHead = nullptr;
  LinkedListNode* smallTail = nullptr;
  LinkedListNode* bigHead = nullptr;
  LinkedListNode* bigTail = nullptr;

  while (head != nullptr) {
    LinkedListNode* nextNode = head->next;
    head->next = nullptr;
    if (head->value < pivot) {
      if (smallHead == nullptr) {
        smallHead = head;
        smallTail = head;
      } else {
        smallTail->next = head;
        smallTail = head;
      }
    } else {
      if (bigHead == nullptr) {
        bigHead = head;
        bigTail = head;
      } else {
        bigTail->next = head;
        bigTail = head;
      }
    }
    head = nextNode;
  }

  if (smallHead == nullptr) {
    return bigHead;
  } else {
    smallTail->next = bigHead;
    return smallHead;
  }
}