快慢指针：链表的中间值问题

小半 • 2023年2月3日上午10:55 • 技术随笔 • 阅读 219

一.快慢指针
快慢指针指的是定义两个指针，这两个指针的移动速度一快一慢，以此来制造出自己想要的差值，这个差值可以然我们找到链表上相应的结点。一般情况下，快指针的移动步长为慢指针的两倍

二.中间值问题
利用快慢指针，我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间节点的目的。
如下图，最开始，slow与fast指针都指向链表第一个节点，然后slow每次移动一个指针，fast每次移动两个指针。

三.代码实现

  public static String getMid(Node first){  //静态使用泛型，编译器报错
        //定义fast、slow两个指针
        Node<String> fast=first;
        Node<String> slow=first;
//使用两个指针遍历链表，当快的指针指向的节点没有下一个时结束，返回慢指针
        while(fast!=null&&fast.next!=null){
        //变换fast和slow的值
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow.data;
    }

假设链表个数为奇数，fast指针走到倒数第二个元素不能再往前走时，由于fast.next依然有值（即最后一个元素），循环会再进行一次，而后fast.next.next=null ，slow会再走一位。
假设链表位n个元素是，slow的位置将指向 n/2+1

===============================================================================================
完整代码及main测试：

public class getMid<T>{
    private static class Node<T> {  //结点类Node, 自定义类泛型
        T data;
        Node next;

        public Node(T item, Node next) {
            this.data = item;
            this.next = next;
        }
    }
    

    public static String getMid(Node first){  //静态使用泛型，编译器报错
        //定义fast、slow两个指针
        Node<String> fast=first;
        Node<String> slow=first;
//使用两个指针遍历链表，当快的指针指向的节点没有下一个时结束，返回慢指针
        while(fast!=null&&fast.next.next!=null){
        //变换fast和slow的值
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow.data;
    }


    public static void main(String[] args) {
        Node<String> first = new Node<String>("aa", null);
        Node<String> second = new Node<String>("bb", null);
        Node<String> third = new Node<String>("cc", null);
        Node<String> fourth = new Node<String>("dd", null);
        Node<String> fifth = new Node<String>("ee", null);
        Node<String> six = new Node<String>("ff", null);
     //   Node<String> seven = new Node<String>("gg", null);

        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = six;
       // six.next = seven;
        System.out.println(getMid(first));
    }
}