【java数据结构与算法学习】快慢指针---快速找到未知长度单链表的中间节点

青旅半醒 2022-05-31 13:41 152阅读 0赞

如题：快速找到未知长度单链表的中间节点

第一种方法是大多人都能想到的方法：先遍历整个链表得到链表的长度，然后遍历链表的一半，找到链表的中间节点。此操作的时间复杂度是O(n)+O(n/2) = O(3n/2),该方法就不再进行代码的展示了。

第二种方法就比较巧妙了，是运用的快慢指针的原理。我们设置两个指针，其中一个指针移动的速度是另一个指针移动速度的两倍，这样当快的指针移动到链表结束位置的时候，慢的指针刚好移动到链表的中间位置。在java中指针就相当于引用。此操作的时间复杂度是O(n/2),因为我们只移动了n/2次。下面我们就开始用代码完成此操作，注意：这段代码我们只针对有头节点的链表。

class Node<AnyType>{
        public AnyType data;
        public Node<AnyType> next;
        public Node(AnyType data,Node next){
            this.data = data;
            this.next = next;
        }
    }
    public class HalfOfLinkedList<AnyType> {
    
        public Node<AnyType> halfOfList(Node<AnyType> p){
            Node<AnyType> fast = p;
            Node<AnyType> slow = p;
            /*
            用异常来做，如果链表为空或者到了链表末尾或者最后剩一步，
            则抛出异常，直接返回慢的节点。
            注意：这里注释写的返回值是一个数组，因为中间元素有时是一个，有时是两个，但是实际该方法我们没有考虑这一点
            try {
                while ((fast = fast.next.next) != null){
                    slow = slow.next;
                }
            }catch (NullPointerException e){
                return new Node[]{slow,slow.next};
            }
            return new Node[]{slow};
    
            */
    
            //fast.next如果为空说明链表是空表或者已经到了表的末尾
            while (fast.next != null){
                //快指针移动两步
                if(fast.next.next != null){
                    //如果最后剩两步，则移动两步
                    fast = fast.next.next;
                    //慢指针移动一步
                    slow = slow.next;
                }else{
                    //如果最后只剩一步，则移动一部
                    fast = fast.next;
                }
            }
            return slow;
        }
    
        public static void main(String[] args) {
            //尾插法，创建链表
            Node<Integer> L = new Node<>(0,null);
            Node<Integer> p = L;
            for (int i = 0; i < 20; i++) {
                 p.next = new Node<>(i+1,null);
                 p = p.next;
            }
    
            System.out.println(new HalfOfLinkedList<Integer>().halfOfList(L).data);
            //System.out.println(new HalfOfLinkedList<Integer>().halfOfList(L)[1].data);
        }
    }