链表也算是基本数据类型之一了。记得刚学习C语言的时候，链表和数组是见得最多的数据类型了。也正因为它的常用，在面试的时候自然会有所涉及，本文主要讨论四道我觉得比较有趣的关于单链表的面试题。

　　Q1 链表的反序

　　Q2 找出链表的中间元素

　　Q3 链表排序

　　Q4 判断一个单链表是否有环

　　以下给出链表结点的数据结构：

　　typedef struct _list_node

　　{

　　double keyVal;

　　struct _list_node *next;

　　}ListNode;

　　Q1 单链表的反序

　　ListNode* reverseList(ListNode* head)

　　{

　　ListNode *p1, *p2 , *p3;

　　//链表为空，或是单结点链表直接返回头结点

　　if (head == NULL || head->next == NULL)

　　{

　　return head;

　　}

　　p1 = head;

　　p2 = head->next;

　　while (p2 != NULL)

　　{

　　p3 = p2->next;

　　p2->next = p1;

　　p1 = p2;

　　p2 = p3;

　　}

　　head->next = NULL;

　　head = p1;

　　return head;

　　}