c语言单链表的逆置、有序性插入、归并
时间: 2023-07-30 10:06:22 浏览: 59
下面是 C 语言单链表的逆置、有序性插入和归并的代码实现:
## 单链表逆置
```c
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while (cur) {
struct ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
```
逆置单链表可以采用迭代或递归的方式实现。上面的代码实现了迭代逆置单链表的方法,具体思路是从头节点开始,每次取出当前节点,将其 next 指针指向前驱节点,然后将前驱节点和当前节点都向后移动一个位置。
## 单链表有序性插入
```c
struct ListNode* insert_node(struct ListNode* head, int val){
struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
new_node->val = val;
new_node->next = NULL;
if (!head){
return new_node;
}
if (val < head->val){
new_node->next = head;
return new_node;
}
struct ListNode* cur = head;
while (cur->next && cur->next->val < val){
cur = cur->next;
}
new_node->next = cur->next;
cur->next = new_node;
return head;
}
```
有序性插入是将一个新节点插入到一个有序单链表中,使得插入后的单链表仍然保持有序。在有序单链表中,每个节点的值都是按照一定的顺序排列的,通常是从小到大或者从大到小。在这段代码中,我们首先判断链表是否为空,如果为空则直接返回新节点。如果新节点的值小于链表头节点的值,则将新节点插入到头节点之前。否则,我们从头节点开始遍历单链表,找到待插入节点的位置,然后将新节点插入到该位置。
## 单链表归并排序
```c
struct ListNode* merge_list(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy->next;
}
struct ListNode* sort_list(struct ListNode* head) {
if (!head || !head->next) {
return head;
}
struct ListNode* slow = head;
struct ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
struct ListNode* l1 = head;
struct ListNode* l2 = slow->next;
slow->next = NULL;
l1 = sort_list(l1);
l2 = sort_list(l2);
return merge_list(l1, l2);
}
```
归并排序是一种经典的排序算法,它的核心思想是分治和合并。在单链表中,我们可以通过快慢指针将单链表分成两个子链表,然后递归地对子链表进行排序,最后将两个有序子链表合并成一个有序链表。
上面的代码实现了归并排序的过程。在 `sort_list` 函数中,我们首先判断链表是否为空或只有一个节点,如果是则直接返回链表。否则,我们使用快慢指针找到链表的中间节点,将链表分成两个子链表,然后递归地对子链表进行排序。在 `merge_list` 函数中,我们使用类似于归并排序的方法将两个有序链表合并成一个有序链表。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)