java 链表的中间值 leetcode算法题

chocoMoss

于 2021-09-26 19:30:33 发布

阅读量130

点赞数

文章标签：链表 leetcode 算法

本文链接：https://blog.csdn.net/chocomoss/article/details/120495230

版权

本文介绍了如何在单链表中找到中间结点，包括使用数组存储、单指针计数和双指针快慢步进三种方法。通过实例展示了每种方法的实现步骤，如数组法通过遍历链表并存储节点，然后返回数组中间位置的节点；单指针法通过两次遍历来确定中间结点；双指针法则利用一个指针每次走两步，当快指针无法继续前进时，慢指针即位于中间结点。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

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

示例

1，2，3，4，5，6，7，8，9  返回5

1，2，3，4，5，6 返回4

方法一：用数组
1、遍历链表
2、将每个元素存进数组
3、数组长度/2的索引就是中间节点

public ListNode middleNode{
        ListNode[] arr = new ListNode[100];
        
        int i = 0;
        
        while(head != null){
            arr[i++] = head;
            head = head.next;
        }

        return arr[i/2];
     }

方法二：单指针
1、遍历链表
2、每遍历一次，记录次数
3、记录完链表，进行第二次遍历
4、循环第一次记录的次数 / 2就得到链表中间节点

public ListNode middleNode{
       int n = 0;
        ListNode cur = head;
        while(cur != null){
            n++;
           cur = cur.next;
		}
		
        int k = 0;
        cur = head;
        while(k < n/2){
            k++;
            cur = cur.next;
        }
        
        return cur;
    }

方法三：双指针（一个快，一个慢）
1、定义两个指针
2、一个指针每次只走一步，另一个每次走两步
3、返回第一个指针

    public ListNode middleNode(ListNode head) {

        ListNode mid = head;

        ListNode fast = head;

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

        return mid;
    }