现有一链表的头指针 ListNode " pHead ,给一定值 x ,编写一段代码将所有小于 x 的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。用c语言写
时间: 2024-12-20 11:20:36 浏览: 3
为了实现这个功能,你可以使用两个指针,一个遍历整个链表并找到第一个大于等于x的节点,另一个用于构建新的有序链表。以下是使用C语言的一个示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 创建一个新的节点
ListNode* newNode(int val) {
ListNode *node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
return node;
}
// 插入新元素到链表前面
ListNode* insertBefore(ListNode* head, int x) {
if (head == NULL || head->val >= x) {
return newNode(x);
}
ListNode* newNode = newNode(x);
newNode->next = head;
return newNode;
}
// 功能实现:重新排列链表
ListNode* rearrangeList(ListNode* pHead, int x) {
ListNode* tail = pHead; // 初始化尾部指针
while (tail != NULL && tail->next != NULL && tail->next->val < x) {
tail = tail->next;
}
ListNode* newHead = tail->next; // 尾部之后的节点作为新链表的头
tail->next = NULL; // 断开原链表
ListNode* current = newHead;
while (current != NULL) {
ListNode* nextTemp = current->next;
current->next = pHead;
pHead = current;
current = nextTemp;
}
return newHead;
}
// 打印链表
void printList(ListNode* head) {
while (head != NULL) {
printf("%d -> ", head->val);
head = head->next;
}
printf("NULL\n");
}
int main() {
// 示例链表初始化
ListNode* pHead = newNode(4);
pHead->next = newNode(2);
pHead->next->next = newNode(1);
pHead->next->next->next = newNode(3);
int x = 5;
pHead = rearrangeList(pHead, x);
printf("Reordered list with x=%d:\n", x);
printList(pHead);
return 0;
}
```
在这个代码中,`rearrangeList` 函数首先找到第一个大于等于 `x` 的节点,然后从那个位置开始重新连接链表。这样就保证了所有小于 `x` 的节点都在大节点之前。
阅读全文