用C语言编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 。
时间: 2023-04-09 10:02:03 浏览: 134
好的,这是一个关于编程的问题,我可以回答。以下是一个用C语言编写的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* partition(ListNode* head, int x) {
ListNode *smallHead = NULL, *smallTail = NULL;
ListNode *largeHead = NULL, *largeTail = NULL;
ListNode *cur = head;
while (cur != NULL) {
if (cur->val < x) {
if (smallHead == NULL) {
smallHead = smallTail = cur;
} else {
smallTail->next = cur;
smallTail = cur;
}
} else {
if (largeHead == NULL) {
largeHead = largeTail = cur;
} else {
largeTail->next = cur;
largeTail = cur;
}
}
cur = cur->next;
}
if (smallHead == NULL) {
return largeHead;
}
smallTail->next = largeHead;
if (largeTail != NULL) {
largeTail->next = NULL;
}
return smallHead;
}
int main() {
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->val = 1;
head->next = (ListNode*)malloc(sizeof(ListNode));
head->next->val = 4;
head->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->val = 3;
head->next->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->next->val = 2;
head->next->next->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->next->next->val = 5;
head->next->next->next->next->next = NULL;
ListNode *newHead = partition(head, 3);
while (newHead != NULL) {
printf("%d ", newHead->val);
newHead = newHead->next;
}
printf("\n");
return 0;
}
```
这个代码使用了两个指针smallHead和largeHead,分别表示小于x和大于或等于x的链表的头结点。遍历原链表,将小于x的结点加入small链表,将大于或等于x的结点加入large链表。最后将small链表的尾结点指向large链表的头结点,返回small链表的头结点即可。
阅读全文