c语言数据结构链表分割
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode* cur = head;
struct ListNode* lesshead,* lesstail,* greaterhead,* greatertail;
lesshead = lesstail = greatertail = greaterhead = NULL;
while(cur)
{
if(cur->val < x)
{
if(lesshead == NULL)
{
lesshead = lesstail = cur;
}
else
{
lesstail->next = cur;
lesstail = cur;
}
}
else
{
if(greaterhead == NULL)
{
greaterhead = greatertail = cur;
}
else
{
greatertail->next = cur;
greatertail = cur;
}
}
cur = cur->next;
}
lesstail->next = greaterhead;
greatertail->next = NULL;
struct ListNode* newNode = lesshead;
return newNode;
}
牛客题，链表分割，在尾插时没有用头结点，我这样写代码对嘛，我运行是有错误的，我怀疑是头节点没有开辟的问题，是这样吗
都没说下，按什么规则分割链表。
整体代码，供参考：
#include <stdio.h>
#include <stdlib.h>
//Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* partition(struct ListNode* pHead, int x)
{
struct ListNode *ph = pHead,*pt = NULL,*p = NULL;
if (!pHead) return NULL; // 链表为空，返回NULL
pHead = NULL;
while (ph){
pt = ph; // 获得链表一个结点
ph = ph->next;
pt->next = NULL;
if (!pHead) // 第一个结点
pHead = pt;
else if (pt->val > x) { // pt结点值 > x 的结点放在链表尾部
p = pHead;
while (p->next) p = p->next;
p->next = pt;
}
else { // pt结点值 <= x 的结点, 插入链表结点值 > x 的结点前
p = pHead;
while (p->next && p->next->val <= x) p = p->next;
if (p == pHead && p->val > x){
pt->next = pHead;
pHead = pt;
}
else {
pt->next = p->next;
p->next = pt;
}
}
}
return pHead;
#if 0 // 以下删除
struct ListNode* cur = head;
struct ListNode* lesshead,* lesstail,* greaterhead,* greatertail;
lesshead = lesstail = greatertail = greaterhead = NULL;
while(cur)
{
if(cur->val < x)
{
if(lesshead == NULL)
{
lesshead = lesstail = cur;
}
else
{
lesstail->next = cur;
lesstail = cur;
}
}
else
{
if(greaterhead == NULL)
{
greaterhead = greatertail = cur;
}
else
{
greatertail->next = cur;
greatertail = cur;
}
}
cur = cur->next;
}
lesstail->next = greaterhead;
greatertail->next = NULL;
struct ListNode* newNode = lesshead;
return newNode;
#endif
}
void print(struct ListNode* pHead)
{
struct ListNode* p = pHead;
if (!pHead)
printf("NULL");
else {
while (p){
printf("%d ", p->val);
p = p->next;
}
}
printf("\n");
}
void creat(struct ListNode ** pHead)
{
int val;
struct ListNode *pt, *p;
(*pHead) = NULL;
while (1){
scanf("%d", &val);
if (val == -1) break;
pt = (struct ListNode*)malloc(sizeof(struct ListNode));
pt->next = NULL;
pt->val = val;
if (!(*pHead))
(*pHead) = pt;
else
p->next = pt;
p = pt;
}
}
int main()
{
struct ListNode *pHead;
creat(&pHead);
print(pHead);
pHead = partition(pHead, 4);
print(pHead);
return 0;
}
运行图：
- 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7479264
- 这篇博客你也可以参考下：【C语言】指针数组 指针数组存储字符串列表（需回看，多次观看）
- 除此之外, 这篇博客: [ C语言 ] 还不懂指针的一定要进来，带你初始指针，简单使用指针，它没有你想的那么难。中的 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
分析：
int main() { float a[5]; float* p; for (p = &a[5]; p >= &a[0];) { *--p = 0; } return 0; }
改进：
for (p = &a[4]; p >= &a[0]; p--) { *p = 0; }
标准规定：允许指向数组元素的指针与指向数组最后一个元素后面的那个内存位置的指针比较，但是不允许与指向第一个元素之前的那个内存位置的指针进行比较。
指针 -- 地址 数组 -- 一组相同类型的数据 int main() { int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; //arr首元素地址 int* p = arr; int i = 0; for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { printf("%p == %p \n", p + i,&arr[i]); } return 0; }分析：
可见数组名和数组首元素的地址是一样的。结论：数组名表示的是数组首元素的地址。那么这样写代码是可行的：int arr[10] = {1,2,3,4,5,6,7,8,9,0};int *p = arr;//p存放的是数组首元素的地址既然可以把数组名当成地址存放到一个指针中，我们使用指针来访问一个就成为可能。int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,0 }; int* p = arr; //指针存放数组首元素的地址 int sz = sizeof(arr) / sizeof(arr[0]); int i = 0; for (i = 0; i < sz; i++) { printf("&arr[%d] = %p <====> p+%d = %p\n", i, &arr[i], i, p + i); } return 0; }
所以 p+i 其实计算的是数组 arr 下标为i的地址
- 您还可以看一下 杨波老师的C语言项目开发系列视频课程课程中的 文件阅读器分析小节, 巩固相关知识点
- 以下回答由chatgpt基于相关博客总结生成:
对于链表的分割操作，是否需要使用头结点取决于具体实现方式。使用头结点的好处是可以方便地在链表头部插入新节点，同时可以避免分割后链表为空的尴尬情况。如果不使用头结点，在进行尾插操作时需要特判空链表的情况。因此建议在实现链表时使用头结点。
关于为什么尾插没有使用头结点而出现错误，具体原因需要看具体实现方式和出错信息。一般来说如果出现错误可能是因为链表操作不当导致链表指针指向了空的地址或者出现了野指针等问题。建议在每次链表操作后都要检查链表的正确性，以及在进行尾插操作时特判空链表的情况。以下是一份基于头结点的链表分割代码示例供参考：
#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node, *LinkedList; LinkedList createList(int arr[], int len) { LinkedList head = (Node*) malloc(sizeof(Node)); head->next = NULL; LinkedList p = head; for (int i = 0; i < len; i++) { LinkedList node = (Node*) malloc(sizeof(Node)); node->data = arr[i]; node->next = NULL; p->next = node; p = p->next; } return head; } void printList(LinkedList head) { LinkedList p = head->next; while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); } LinkedList splitList(LinkedList head, int x) { LinkedList h1 = (Node*) malloc(sizeof(Node)); h1->next = NULL; LinkedList p1 = h1; LinkedList h2 = (Node*) malloc(sizeof(Node)); h2->next = NULL; LinkedList p2 = h2; LinkedList p = head->next; while (p) { if (p->data < x) { p1->next = p; p1 = p1->next; } else { p2->next = p; p2 = p2->next; } p = p->next; } p1->next = NULL; p2->next = NULL; head->next = h1->next; p1->next = h2->next; free(h1); free(h2); return head; } int main() { int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9}; int len = sizeof(arr) / sizeof(int); LinkedList head = createList(arr, len); printf("Original list: "); printList(head); int x; printf("Enter x: "); scanf("%d", &x); head = splitList(head, x); printf("Split list: "); printList(head); return 0; }