深入链表的遍历——快慢指针算法（LeetCode——876题）

今天我们一起来学习一下一个快速遍历链表的方法

我们先来看看一道经典的需要遍历链表的题目 （题目来自LeetCode）

876. 链表的中间结点https://leetcode.cn/problems/middle-of-the-linked-list/

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

普通方法

    public ListNode middleNode(ListNode head) {ListNode dummy = new ListNode(0, head);ListNode current = dummy;int sum=0;while(current.next!=null){sum++;current=current.next;}for(int i=0;i<sum/2;i++){dummy=dummy.next;}return dummy.next;}

第一个循环遍历了整个链表来计算链表的长度（存储在变量 sum 中）。这个循环的时间复杂度是 O(n)，因为它必须访问链表中的每个节点一次。 

第二个循环根据链表的长度的一半（sum / 2）再次遍历链表，直到到达中间节点。虽然这个循环看起来像是减少了遍历的次数（因为它只遍历了链表的一半），但由于第一个循环已经遍历了整个链表，所以总体时间复杂度仍然是 O(n)。 

快慢指针算法 

    public ListNode middleNode(ListNode head) {ListNode slow=head;ListNode fast=head;while(fast!=null &&fast.next!=null){fast=fast.next.next;slow=slow.next;}return slow;}

在这个优化版本中，我们使用两个指针，一个快指针（fast）和一个慢指针（slow）。快指针每次移动两步，而慢指针每次移动一步。当快指针到达链表末尾（或倒数第二个节点，如果链表长度为奇数）时，慢指针正好位于链表的中间。这种方法的时间复杂度为O(n)，但因为它只遍历链表一次，所以比原来的方法更高效。 

对比 

虽然两个方法的时间复杂度都是 O(n)，但是实际上普通方法需要遍历n次来计算长度，然后再遍历n/2次来找到中间节点，总共是1.5n次。而快慢指针算法只需要遍历n次就找到了中间节点。在面对大量的数据时，还是有些许的优势的。