建立一个单链表建立一个顺序表

建立单链表的代码如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* createLinkedList(vector<int>& nums) {
    ListNode* head = new ListNode(0);
    ListNode* p = head;
    for (int i = 0; i < nums.size(); i++) {
        ListNode* node = new ListNode(nums[i]);
        p->next = node;
        p = p->next;
    }
    return head->next;
}

建立顺序表的代码如下：

const int MAXN = 100;
int a[MAXN];

void createArray(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        a[i] = nums[i];
    }
}

相关问题

用尾插法建立一个单链表

### 回答1：
好的，我可以回答这个问题。尾插法建立单链表的步骤是：首先创建一个头节点，然后依次读入数据，每次在链表末尾添加一个节点，直到读完所有数据。具体实现过程可以参考下面的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createLinkedList() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    Node* tail = head;
    int x;
    while (scanf("%d", &x) != EOF) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = x;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

int main() {
    Node* head = createLinkedList();
    Node* p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return 0;
}

以上代码是用 C 语言实现的，可以根据具体需求进行修改。

### 回答2：
尾插法建立单链表是一种常见的链表建立方法，其核心思想是从链表的尾部逐个插入元素。

首先，我们定义单链表的节点结构如下：

struct Node { 
    int data; // 数据域
    struct Node* next; // 指针域
};

然后，我们可以按照以下步骤来使用尾插法建立单链表：

1. 创建一个头节点，并将其指针域初始化为NULL。
2. 创建一个当前节点指针temp，并将其指向头节点。
3. 输入需要插入的元素值，创建一个新节点，并将该元素值赋值给新节点的数据域。
4. 判断当前链表是否为空，如果为空，则将新节点赋值给temp的指针域，并将temp指针指向新节点。
5. 如果链表不为空，则循环找到链表的尾部节点，即temp指针指向的节点的指针域为NULL。在循环中，将temp指针指向下一个节点，直到temp指向的节点的指针域为空。
6. 将新节点赋值给temp指针指向的节点的指针域，使其指向新节点，并更新temp指针指向新节点。
7. 重复步骤3-6，直到插入完所有的元素。
8. 打印链表中的元素，可以通过循环遍历链表的每个节点，将节点的数据域打印出来。

使用尾插法建立单链表时，可以方便地在链表的尾部插入新的元素，不需要像头插法那样进行反转操作。

### 回答3：
尾插法是一种在单链表尾部插入新节点的建立单链表的方法。下面是用尾插法建立一个单链表的过程：

1. 首先创建一个头节点，头节点的指针域为空。
2. 创建一个指向头节点的指针，称为p。
3. 初始化一个计数器count，用于记录当前链表中节点的个数。
4. 输入一个整数n，表示待插入节点的个数。
5. 判断count是否小于n，如果是则继续执行下面的步骤，否则结束。
6. 创建一个新节点，并输入该节点的数据。
7. 将新节点的指针域指向空。
8. 将p的指针指向新节点。
9. 更新p的指针为新节点。
10. 将count加1。
11. 返回步骤5。
12. 输出建立完成的单链表。

使用尾插法建立的单链表，每次插入新节点时都是在链表的尾部进行操作，因此可以保持节点的插入顺序不变。这种方法适用于需要按照节点的输入顺序建立一个单链表的场景，时间复杂度为O(n)。

例如，按照尾插法建立一个包含4个节点的单链表，输入的整数n为4，数据依次为1、2、3、4，则建立完成的单链表如下所示：

头节点 -> 节点1 -> 节点2 -> 节点3 -> 节点4 -> NULL

其中，头节点的指针域指向节点1，节点1的指针域指向节点2，以此类推，节点4的指针域指向NULL。

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

为两部分，比基准小的节点在前面，大于等于基准的节点在后面。可以使用额外的空间，要求算法时间复杂度为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;
  }
}