1.链表反转
大家有没有过将链表反转的想法，与数组反转不同的是这里的反转后是将每个节点的地址白村反过来，当然也可以遍历链表然后从尾节点开始尾插到新链表中，然后将新链表的头结点返回即可。我们今天要学的是第一个方法。当然第二个想法也没问题，只不过第一种想法较为高级一些。
代码实现：
ListNode* reverseList(ListNode* phead)
{
//处理空链表
if (phead == NULL)
{
return phead;
}
//创建三个指针
ListNode* n1, *n2, *n3;
n1 = NULL, n2 = phead, n3 = phead->next;
while (n2)
{
//修改n2的指向
n2->next = n1;
//修改三个指针的位置
n1 = n2;
n2 = n3;
if (n3)
{
n3 = n3->next;
}
}
return n1;//此时n1刚好为新链表的头节点
}我们可以看到我们创建了三个指针，分别指向第一个节点，和下一个节点，我们通过判断n2是否为空，来控制循环，此时n1就来到了原链表的尾节点，通过更改节点们的指针域来改变节点的指向。此时原链表就达到了意义上的反转，大家可能会问为啥不是使用二级指针，因为我们我们只是改变其指针域，并不改变节点的数据。当然n1=NULL,是为了方便打印链表时停下。我们也可以在打印是加上->来使其更好理解。
我们来试试：
我们可以看到利用尾插代码创建了1->2->3->4->5->NULL的链表，调用函数后进行了反转。我们在后面有又打印一个NULL是让大家更容易理解，其实打印代码到NULL时就会停下的。改变后的代码为NULL<-1<-2<-3<-4<-5其实5后面还有一个NULL但是我们将5作为头节点打印就不会显示出来。
2.分割链表
所谓的分割链表其实就是指定一个数，将小于该数的都放在该数的前面。
例如：1 2 9 3 6 4 如果指定数为返回的链表就为1 2 9 3 6 4，就是只管小于它的放在前面，其他不管。
代码演示：
ListNode* partition(ListNode* phead, int x)
{
if (phead == NULL)
{
return phead;
}
//创建带头的大小的链表
ListNode* lessHead, * lessTail;
ListNode* greaterHead,* greaterTail;
lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
if (lessHead==NULL && lessTail==NULL)
{
perror("malloc");
}
if (greaterHead==NULL && greaterTail==NULL)
{
perror("malloc");
}
//遍历原链表，将节点放在对应的新链表中
ListNode* pcur = phead;
while (pcur)
{
if (pcur->val < x)
{
//放在小链表中
lessTail->next = pcur;
lessTail = lessTail->next;
}
else//放在大链表中
{
greaterTail->next = pcur;
greaterTail = greaterTail->next;
}
pcur = pcur->next;
} greaterTail = NULL;//防止死循环
//将小链表和大链表进行首尾相连
lessTail->next = greaterHead->next;
ListNode* ret = lessHead->next;
free(greaterHead);
free(lessHead);
return ret;
}此代码就是遍历原链表将小于指定数的节点放入一个链表中，大的也放入一个链表中，然后将小链表的尾结点与大链表的头结点相连，但要注意的是我们的大链表的尾结点可能还连着一个节点，导致链表成为一个闭环，所以还需要将大链表的尾结点的指针域保存NULL.
我们可以测试一下：
我们还是采用尾插代码创建一个链表，并选中3为指定数，预计输出结果就为1 2 4 3 5 4 6
我们输出了相应的结果，可以看得出代码很成功。
