链表是我们数据结构面试中比较容易出错的问题，所以很多面试官总喜欢在这上面下功夫，为了避免出错，我们最好先进行全面的分析。在实际软件开发周期中，设计的时间通常不会比编码的时间短，在面试的时候我们不要着急于写代码，而是一开始仔细分析和设计，这将给面试官留下一个很好的印象。
与其很快写出一段千疮百孔的代码，不容仔细分析后再写出健壮性无敌的程序。
面试题：输入一个单链表的头结点，返回它的中间元素。为了方便，元素值用整型表示。
当应聘者看到这道题的时候，内心一阵狂喜，怎么给自己遇到了这么简单的题。拿起笔就开始写，先遍历整个链表，拿到链表的长度 len，再次遍历链表，位于 len/2 的元素就是链表的中间元素。
所以这个题最重要的点就是拿到链表的长度 len。而拿到这个 len 也比较简单，只需要遍历前设定一个 count 值，遍历的时候 count++ ，第一次遍历结束，就拿到单链表的长度 len 了。
于是我们很快写出了这样的代码：
public class Test15 { public static class LinkNode { int data; LinkNode next; public LinkNode(int data) { this.data = data; } } private static int getTheMid(LinkNode head) { int count = 0; LinkNode node = head; while (head != null) { head = head.next; count++; } for (int i = 0; i < count / 2; i++) { node = node.next; } return node.data; } public static void main(String[] args) { LinkNode head = new LinkNode(1); head.next = new LinkNode(2); head.next.next = new LinkNode(3); head.next.next.next = new LinkNode(4); head.next.next.next.next = new LinkNode(5); System.out.println(getTheMid(head)); } }面试官看到这个代码的时候，他告诉我们上面代码循环了两次，但是他期待的只有一次。
于是我们绞尽脑汁，突然想到了网上介绍过的一个概念：快慢指针法。
假设我们设置两个变量 slow、fast 起始都指向单链表的头结点当中，然后依次向后面移动，fast 的移动速度是 slow 的 2 倍。这样当 fast 指向末尾节点的时候，slow 就正好在正中间了。
想清楚这个思路后，我们很快就能写出如下代码：
public class Test15 { public static class LinkNode { int data; LinkNode next; public LinkNode(int data) { this.data = data; } } private static int getTheMid(LinkNode head) { LinkNode slow = head; LinkNode fast = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow.data; } public static void main(String[] args) { LinkNode head = new LinkNode(1); head.next = new LinkNode(2); head.next.next = new LinkNode(3); head.next.next.next = new LinkNode(4); head.next.next.next.next = new LinkNode(5); System.out.println(getTheMid(head)); } } 快慢指针法举一反三快慢指针法 确实在链表类面试题中特别好用，我们不妨在这里举一反三，对原题稍微修改一下，其实也可以实现。
面试题：给定一个单链表的头结点，判断这个链表是否是循环链表。
和前面的问题一样，我们只需要定义两个变量 slow，fast，同时从链表的头结点出发，fast 每次走链表，而 slow 每次只走一步。如果走得快的指针追上了走得慢的指针，那么链表就是环形(循环)链表。如果走得快的指针走到了链表的末尾（fast.next 指向 null）都没有追上走得慢的指针，那么链表就不是环形链表。
有了这样的思路，实现代码那还不是分分钟的事儿。
public class Test15 { public static class LinkNode { int data; LinkNode next; public LinkNode(int data) { this.data = data; } } private static boolean isRingLink(LinkNode head) { LinkNode slow = head; LinkNode fast = head; while (slow != null && fast != null && fast.next != null) { if (slow == fast || fast.next = slow) { return true; } fast = fast.next.next; slow = slow.next; } return false; } public static void main(String[] args) { LinkNode head = new LinkNode(1); head.next = new LinkNode(2); head.next.next = new LinkNode(3); head.next.next.next = new LinkNode(4); head.next.next.next.next = new LinkNode(5); System.out.println(isRingLink(head)); head.next.next.next.next.next = head; System.out.println(isRingLink(head)); } }确实有意思，快慢指针法 再一次利用它的优势巧妙解决了我们的问题。
快慢指针法的延展我们上面讲解的「快慢指针法」均是一个变量走 1 步，一个变量走 n 步。我们其实还可以拓展它。这个「快慢」并不是说一定要同时遍历。
比如《剑指Offer》中的第 15 道面试题，就运用到了「快慢指针法」的延展。
面试题：输入一个单链表的头结点，输出该链表中倒数第 k 个节点的值。