分割链表题解

提供三种思路:

1.再原链表上进行修改，定义一个指针pcur指向头结点。当pcur指向的节点的值小于x，pcur直接往后走，如果pcur指向的节点的值大于x，删除pcur指向的节点，并将这个节点尾插到链表后面

2.创建一个新链表，遍历原链表，若pcur节点的值小于x，头插在新链表中；若pcur节点的值大于或等于x，尾插在新链表中

3.创建新链表:小链表和大链表；小链表存放的都是小于x的节点，大链表存放的都是大于x的节点，然后让小链表的尾结点和大链表的第一个节点相连。

代码如下:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode LSTNode;//重命名方便使用
struct ListNode* partition(struct ListNode* head, int x) {if(head==NULL)//判断链表是否为空{return head;}//链表不为空://创建小链表和大链表LSTNode *lesshead,*lesstail;//小链表的头和尾LSTNode *greaterhead,*greatertail;//大链表的头和尾lesshead=lesstail=(LSTNode*)malloc(sizeof(LSTNode));//给节点申请空间greaterhead=greatertail=(LSTNode*)malloc(sizeof(LSTNode));//给节点申请空间//遍历原链表，将原链表的节点尾插到大小链表中LSTNode *pcur=head;while(pcur){if(pcur->val<x)//给定值小于x{//尾插到小链表lesstail->next=pcur;lesstail=lesstail->next;}else{//尾插到大链表中greatertail->next=pcur;greatertail=greatertail->next;}pcur=pcur->next;//pcur往后移动}greatertail->next=NULL;//大链表尾结点要指向NULL，防止死循环lesstail->next=greaterhead->next;LSTNode *ret=lesshead->next;free(lesshead);free(greaterhead);lesshead=greaterhead=NULL;return ret;
}