链表中涉及”快慢指针“的编程题—“返回中间节点”
业务要求：
给一个带有头节点 head 的非空单链表，返回链表的中间节点，如果有两个中间节点，则返回第二个中间节点。
一般思路 ：
可以遍历完一遍链表，获得链表的长度 length。然后继续通过获得的链表的长度，如果该长度为偶数，则有两个中间节点，再遍历(length/2) 步，返回的就是第二个中间节点；如果该长度为奇数，则有一个中间节点,再遍历（length/2 步，返回的就是中间节点。
分析 ：
可以知道，我们这里的遍历需要遍历链表一次加上（length/2)步，也就是遍历 1.5 次。
代码 ：
public ListNode middleNode() { if (head == null) { return null; } int length = 0; ListNode cur = head; while (cur != null) { cur = cur.next; length++; } int size2 = length / 2; cur = head; while (size2 != 0) { cur = cur.next; size2--; } return cur; }
测试结果
准备的链表储存了这样的数据{10,23,2,53} 然后调用我们准备好的middleNode()方法 即：System.out.println( myLinkedList.middleNode().var); 返回的结果为：2 准备的链表储存了这样的数据{10,23,2,53，34} 然后调用我们准备好的middleNode()方法 即：System.out.println( myLinkedList.middleNode().var); 返回的结果为：2
进阶思路
分析
- 上述我们实现的过程中，我们一共遍历链表 1.5 次，那么我们是否可以在遍历 1 次就完成业务要求呢？
答案是有的，这个时候我们可以借助两个指针，也就是 “快慢指针” 来实现。 - fast = 2 个/步；fast 一步遍历两个节点
- slow = 1 个/步；slow 一步遍历一个节点
- 那么相同的步数内，fast 遍历的节点总数是 slow 节点遍历的节点总数的两倍。
图形化理解
通过图形我们就可以知道使用 “快慢指针” 只用遍历一遍链表就能完成业务要求
代码
public ListNode middleNode1() { if (head == null) { return null; } ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next; slow = slow.next; } return slow; }
注意事项
- 先判断链表是否为空，若为空链表则返回 null
- whlie 条件语句的循环条件必须是&&连接
- while 条件语句的循环条件必须先判断 fast！= null，因为 fast 在 fast. next 的前面，如果没有 fast 也就没有 fast. next
