876--Middle Of The Linked List

佚名 5年前 (2019-08-15) 算法 1666人围观抢沙发百度已收录

package LinedList;

import java.util.LinkedList;
import java.util.List;

public class MiddleOfTheLinkedList {
    // 解法一：求到链表长度，然后再去中间节点。
    public ListNode middleNode(ListNode head) {
        ListNode middleNode =head;
        int size=1;
        while (middleNode.next!=null){
            middleNode=middleNode.next;
            size++;
        }
        middleNode=head;
        for (int i=1;i<(size/2)+1;i++){
            middleNode= middleNode.next;
        }
        return middleNode;
    }
    //解法二：解法一的目的就是找到索引，所以可以直接将节点放入数组中，然后取中间节点即可，
    //        省去了再次遍历。
    public ListNode middleNode2(ListNode head) {
        List<ListNode> list=new LinkedList<>();
        ListNode current=head;
        while (current!=null){
            list.add(current);
            current=current.next;
        }
        return list.get((list.size()/2));
    }
    //解法三：快慢指针，遍历链表时，慢指针速度为一，快指针速度为二。
    //          则快指针遍历完时，慢指针就指向中间节点。
    public ListNode middleNode3(ListNode head) {
       ListNode slow=head;
       ListNode fast=head;
       while (fast!=null&&fast.next!=null){
           slow=slow.next;
           fast=fast.next.next;
       }
       return slow;
    }
}