链表oj测试题（下）

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.

我们可以测试一下：