写一个c++的函数用来建立非递减有序链表,并解释每一行的作用
时间: 2023-06-26 10:08:49 浏览: 65
以下是一个建立非递减有序链表的C++函数,每一行代码的作用已经在注释中说明:
```c++
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* insertNode(ListNode* head, int val) {
ListNode* newNode = new ListNode(val); // 创建一个新结点
if (head == NULL) { // 如果链表为空,则直接将新结点作为头结点返回
return newNode;
}
if (newNode->val < head->val) { // 如果新结点的值小于头结点的值,则将新结点插入到头结点之前
newNode->next = head;
return newNode;
}
ListNode* cur = head;
while (cur->next != NULL && cur->next->val <= newNode->val) { // 遍历链表,找到第一个比新结点值大的结点
cur = cur->next;
}
newNode->next = cur->next; // 将新结点插入到该结点之前
cur->next = newNode;
return head; // 返回头结点
}
ListNode* buildSortedLinkedList(vector<int>& nums) {
ListNode* head = NULL;
for (int i = 0; i < nums.size(); i++) { // 遍历数组
head = insertNode(head, nums[i]); // 将数组元素依次插入链表中
}
return head; // 返回头结点
}
```
该函数会先遍历给定的数组,然后创建一个非递减有序链表,最后返回该链表的头结点。
在 insertNode 函数中,如果链表为空,则直接将新结点作为头结点返回;如果新结点的值小于头结点的值,则将新结点插入到头结点之前;否则,遍历链表,找到第一个比新结点值大的结点,将新结点插入到该结点之前。
在 buildSortedLinkedList 函数中,遍历给定的数组,将数组元素依次插入链表中,并返回头结点。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)