链表是很重要的数据结构，许多都依赖于链表构建。比如哈希表开放链表构建法等。作为如此重要的数据结构，链表是面试笔试的重要考核点。这里，就对几个经典的链表算法笔试题做一个归纳汇总。 1. 反转链表 这是一个简单题，对于熟悉链表的人来说很简单。对于不懂的人来说就是一个拦路虎。话不多说，上leetcode原题。
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ struct ListNode* curr = NULL; struct ListNode* prev = head; struct ListNode* temp = NULL; while (prev) { temp = prev->next; prev->next = curr; curr = prev; prev = temp; } return curr; }怎么理解呢？ 这是初始的正向链表。 进行初始化。 开始循环，赋值阶段。temp = prev->next prev->next = curr 开始将链表结点的指向反转。 完成上一个结点指向反转后，将结点后移。curr = prev prev = temp。 然后再进行下一个循环。直至到终点就完成了链表反转。 最后指针结点curr指向了原链表的尾结点即反转后链表的头节点。返回curr即可。
2. 返回链表中间的结点 这个题就是典型的快慢指针。
示例 ： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head){ struct ListNode* fast = head; struct ListNode* slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; }这种题很多，比如返回倒数第二个结点啊什么的，都可以用快慢指针。
3. 证明链表是否相交
给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
如果两条链表相交，则必然为这样。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* nodeA = headA; struct ListNode* nodeB = headB; while (nodeA != nodeB) { if (nodeA == NULL) { nodeA = headB; } else { nodeA = nodeA->next; } if (nodeB == NULL) { nodeB = headA; } else { nodeB = nodeB->next; } } return nodeA; }链表A从头走到尾，B也从头走到尾。当A走到尾，再走B的路线。反之亦然。因为速度一样，都走A和B两条路径。如果相交，则必然会走到重合结点。如果不相交，最后也都会走到NULL结点返回。
4. 环路检测
给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。 有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。 示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 输入：head = [1], pos = -1 输出：no cycle 解释：链表中没有环。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast = head; struct ListNode* slow = head; while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; if (fast == slow) { fast = head; while (fast != slow) { fast = fast->next; slow = slow->next; } return fast; } } return NULL; }这个也是双指针，为何这么做可以呢，这需要数学证明。
如果链表中有环，那么快慢指针就一定可以相遇（且一定再环上，如图上的c点），此时快指针移动过的距离是慢指针的2倍，根据图中的参数，我们可以写出以下等式：
(m+y)*2=m+xn+y //这里的xn是当相遇时快指针已经在环上循环了x次，x>=1且为整数 => m+y=xn => m=n-y+(x-1)*n //下面解释为什么写成这种形式
接下来将快指针置于表头(此时快指针在a处，慢指针在c处)，与慢指针以相同速度在链表上移动，当快指针移动到b处时，移动了m的距离，根据上面的等式可知，慢指针移动了n-y+(x-1)*n的距离。
我们来分析一下此时的慢指针在什么位置： 先移动(x-1)*n的距离，相当于在环上循环了(x-1)次，慢指针又回到了c点，然后再移动n-y的距离，如图所示，n-y正好是c点到b点的距离，说明此时慢指针也移动到了b点，即快慢指针在环路的开头节点相遇了。
