20天刷题计划-876. 链表的中间结点

简介: 思路如下:先遍历一次,计算链表的长度,判断链表长度是奇数还是偶数,然后计算中间节点的下标值,偶数结点的时候,得到的是中间的第二个结点,然后再遍历一次,在链表头节点遍历N/2次就得到了链表的中间节点。

一、题目描述:

给定一个头结点为 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,我们返回第二个结点。
提示:
给定链表的结点数介于 1 和 100 之间。

二、思路分析:

分析题目,注意点如下:

  • 给定链表的结点数介于 1100 之间。
  • 如果有两个中间结点,则返回第二个中间结点

思路如下:

先遍历一次,计算链表的长度,判断链表长度是奇数还是偶数,然后计算中间节点的下标值,偶数结点的时候,得到的是中间的第二个结点,然后再遍历一次,在链表头节点遍历N/2次就得到了链表的中间节点。

三、AC 代码:

public ListNode middleNode(ListNode head) {
        int length = 0;
        ListNode temp = head;
        while(temp != null){
            length++;
            temp = temp.next;
        }
        int middle = length / 2;
        for(int i = 0;i < middle;i++){
            head = head.next;
        }
        return head;
    }

四、总结:

image-20220311174719861

想法比较简单,遍历可以得出结果,看到力扣中大家的题解方法,发现这道题更适合使用快慢指针的方法,也算是了解了快慢指针的做法,代码如下(官方解法代码),之前都不知道有快慢指针的方式。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}



相关文章
|
1月前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
65 1
|
3月前
|
程序员
【刷题记录】移除链表元素
【刷题记录】移除链表元素
|
20天前
|
存储 算法 搜索推荐
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念,通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中,理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
10 1
|
2月前
链表的中间结点
链表的中间结点
178 57
|
1月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
16 0
|
3月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
27 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
3月前
|
算法
LeetCode第19题删除链表的倒数第 N 个结点
该文章介绍了 LeetCode 第 19 题删除链表的倒数第 N 个结点的解法,通过使用快慢双指针,先将快指针移动 n 步,然后快慢指针一起遍历,直到快指针到达链尾,从而找到倒数第 N 个结点的前一个结点进行删除,同时总结了快慢指针可减少链表遍历次数的特点。
LeetCode第19题删除链表的倒数第 N 个结点
|
3月前
【刷题记录】链表的回文结构
【刷题记录】链表的回文结构
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
54 5
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
41 4