现有一链表的头指针head,给定一个值x,编写一段代码将所有小于x的结点排在其余结点之前,且不改变原来的数据顺序,返回重新排列后的链表头指针。,用c语言实现
时间: 2024-12-25 16:24:54 浏览: 6
在C语言中,你可以通过遍历链表并利用迭代的方式来实现这个功能。首先,我们需要创建一个新的链表结构体,然后定义两个指针,一个指向当前节点,一个指向新链表的头部。当遍历到一个值小于x的节点时,我们将其添加到新链表的开头,然后继续遍历原链表。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 插入节点到新链表头部
ListNode* insertToNewHead(ListNode* new_head, ListNode* node) {
if (node->val >= x) {
return new_head; // 如果大于等于x,直接返回,不插入
}
node->next = new_head; // 将节点插入到新链表的头部
return node;
}
// 重新排列链表
ListNode* rearrangeList(ListNode* head, int x) {
ListNode *new_head = NULL, *current = head;
while (current != NULL) {
if (current->val < x) {
current = insertToNewHead(new_head, current);
} else {
if (new_head == NULL) {
new_head = current;
}
current = current->next;
}
}
return new_head;
}
// 打印链表
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
printf("%d ", temp->val);
temp = temp->next;
}
printf("\n");
}
int main() {
// 创建示例链表
ListNode* head = malloc(sizeof(ListNode));
head->val = 5;
head->next = malloc(sizeof(ListNode));
head->next->val = 3;
head->next->next = malloc(sizeof(ListNode));
head->next->next->val = 8;
head->next->next->next = malloc(sizeof(ListNode));
head->next->next->next->val = 4;
int x = 6;
head = rearrangeList(head, x);
printf("Reordered list with values less than %d:\n", x);
printList(head);
return 0;
}
```
这段代码首先定义了链表节点结构,接着实现了`rearrangeList`函数,该函数会返回一个新链表的头指针。在主函数中,我们创建了一个链表,并设置x的值为6,然后对链表进行了排序。最后打印出排序后的链表。
阅读全文