LeetCode：Find Middle Node （查找中间节点）

迈不过友情╰ 2022-05-08 05:50 161阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录**

1. 查找单链表的中间节点

2.题目分析：

3.题目解决:

4.源码github地址：

--------------------

### 1. 查找单链表的中间节点 ###

链表是基本的数据结构之一，面试题中链表占很大一部分，可见链表操作是非常重要的。我对一些常见的链表操作进行的归纳。

--------------------

### 2.题目分析： ###

链表的特点就是有很多的节点，每个节点有数据域和指针域两部分，指针域存放的是下一个节点的地址，根据地址找到下一个节点。链表只能从前到后遍历，不能从后到前遍历。对于这个问题，我们首先能够想到的就是先遍历一遍整个的链表，然后计算出链表的长度，进而遍历第二遍找出中间位置的数据。这种方式非常简单。

--------------------

### 3.题目解决: ###

若题目要求只能遍历一次链表，那又当如何解决问题？可以采取建立两个指针，一个指针一次遍历两个节点，另一个节点一次遍历一个节点，当快指针遍历到空节点时，慢指针指向的位置为链表的中间位置，这种解决问题的方法称为快慢指针方法。（面试尽量用这种方式，能够提高印象分）

public Node findMiddleNode(Node node) {
        if (node == null) {
           return null;
        }
        Node fast = node;
        Node slow = node;
        while (fast.next != null && fast.next.next != null) {
          fast = fast.next.next;
          slow = slow.next;
        }
        return slow;
      }

时间复杂度：O(n)

空间复杂度：O(1)

--------------------

### 4.源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode