【Java版oj】链表的中间结点

曾经终败给现在 2024-04-03 14:04 89阅读 0赞

**目录**

一、原题再现

二、问题分析

三、完整代码

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

> ## 一、原题再现 ##
> 
> [876. 链表的中间结点][876.]
> 
> 难度简单715
> 
> 给定一个头结点为 `head` 的非空单链表，返回链表的中间结点。
> 
> 如果有两个中间结点，则返回第二个中间结点。
> 
> **示例 1：**
> 
>     输入：[1,2,3,4,5]
>     输出：此列表中的结点 3 (序列化形式：[3,4,5])
>     返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
>     注意，我们返回了一个 ListNode 类型的对象 ans，这样：
>     ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
> 
> **示例 2：**
> 
>     输入：[1,2,3,4,5,6]
>     输出：此列表中的结点 4 (序列化形式：[4,5,6])
>     由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

> ## 二、问题分析 ##
> 
> 方法一：非技巧性。统计链表中结点个数。遍历链表，求取链表所有结点个数，在/2找到中间结点。因为需要遍历所有元素结点，其空间复杂度是O(1)，时间复杂度是O(n)。
> 
> 方法二：技巧性。链表oj中常用思路：双指针遍历思路
> 
> 慢引用：一次向后跳一步
> 
> 快引用：一次向后跳两步
> 
> ![a4971ee2ce2c485dbc82557773442131.png][]
> 
> 逻辑上两个引用同步走，当快引用到达结尾时，慢引用在中间位置。
> 
> 注意：快慢引用的方式有很多种需要自己判断，使其在链表结点元素为奇数和偶数的情况下同样适用。
> 
> 根据题目要求如果有两个中间结点，则返回第二个中间结点。
> 
> 故而此时用的是：快->判断->慢->快->判断
> 
> 如图所示：
> 
> ![46bb725b1e754db99fd30e0c02602e25.png][]
> 
> ![7414051fb95d4f2f8c59809094d95b86.png][]

> ## 三和、完整代码 ##
> 
> 方法一：
> 
> 时间复杂度：O(n)
> 
> 空间复杂度：O(1)
> 
>     /**
>      * Definition for singly-linked list.
>      * public class ListNode {
>      *     int val;
>      *     ListNode next;
>      *     ListNode() {}
>      *     ListNode(int val) { this.val = val; }
>      *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
>      * }
>      */
>     class Solution {
>         private int sizeOf(ListNode head){
>                 int count=0;
>                 for(ListNode cur=head;cur!=null;cur=cur.next){
>                     count++;
>                 }
>                 return count;
>             }
>         public ListNode middleNode(ListNode head) {
>             ListNode cur=head;
>             int size=sizeOf(head);
>             for(int i=0;i<size/2;i++){
>                 cur=cur.next;
>             }
>             return cur;
>         }
>     }
> 
> ![b4bbd0573066465cb6275c53b05d3a05.png][]
> 
> 方法二：
> 
> 时间复杂度：O(n)
> 
> 空间复杂度：O(1)
> 
>     /**
>      * Definition for singly-linked list.
>      * public class ListNode {
>      *     int val;
>      *     ListNode next;
>      *     ListNode() {}
>      *     ListNode(int val) { this.val = val; }
>      *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
>      * }
>      */
>     class Solution {
>         public ListNode middleNode(ListNode head) {
>            if (head == null) {
>                     return null;
>                 }
>             ListNode fast = head;
>             ListNode slow = head;
>     
>             while (true) {
>                 fast = fast.next;
>                 if (fast == null) {
>                     break;
>                 }
>                 slow = slow.next;
>                 fast = fast.next;
>                 if (fast == null) {
>                     break;
>                     }
>                 }
>             return slow;
>         }
>     }
> 
> ![150f05a7f4e5486096ead04dced9cded.png][]

![091d2641148d4f25bc3978da03ef17cb.png][]

[876.]: https://leetcode.cn/problems/middle-of-the-linked-list/
[a4971ee2ce2c485dbc82557773442131.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/74078de495e448b189b833a5bd3a7424.png
[46bb725b1e754db99fd30e0c02602e25.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/468e257b8f2e4270ac12d86a6ab954f7.png
[7414051fb95d4f2f8c59809094d95b86.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/cd633573a5e5481d94592028935a58b6.png
[b4bbd0573066465cb6275c53b05d3a05.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f3aa2c39735241b7938e7b3032fbc3d9.png
[150f05a7f4e5486096ead04dced9cded.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a12a281daa334c0883fe8327792a2422.png
[091d2641148d4f25bc3978da03ef17cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/cb95ceeb9ed9461d9b3847b48c64c6ea.png