题目要求

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点(链表长度为偶数),则返回第二个中间结点。

比如链表[1,2,3,4,5]的中间节点是3,[1,2,3,4,5,6]的中间节点是4。

数组法

我首先想到的是将节点存入ArrayList,然后通过列表长度去找到中间节点,实现如下:

public  ListNode middleNode(ListNode head) {
    //思路1:循环遍历将链表每一个节点存入Array list,然后求列表的中间元素

    //创建array list
    ArrayList<ListNode> list = new ArrayList<>();

    //遍历链表,将节点入list
    ListNode curr = head;

    while (curr != null){
        list.add(curr);
        curr = curr.next;
    }

    //根据list长度求出链表的中间节点
    return list.get((list.size() /2));

这种方式最容易想到,但是结果最为不好,效率太低,所以得到的结果是:

执行用时 :1 ms, 在所有 Java 提交中击败了14.48%的用户
内存消耗 :34.8 MB, 在所有 Java 提交中击败了39.90%的用户

快慢指针

定义两个指针,fast、low。初始值都指向head,在while循环中fast移动两次,low移动一次。因此,fast指针比Low指针块两倍。

  • 当链表长度为奇数时,fast指向最后一个节点,low指向中间节点。
  • 当链表长度为偶数时,fast指向最后一个节点的前一个节点,low指向第二个中间节点。

public ListNode middleNode(ListNode head) {
    //思路二:利用快慢指针
    ListNode fast = head;
    ListNode low = head;

    while(fast != null && fast.next != null ){
        fast = fast.next.next;
        low = low.next;
    }

    return low;
}