Leecode 876. 链表的中间结点

简介: Leecode 876. 链表的中间结点

题目描述:

给定一个带有头结点 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,我们返回第二个结点。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/middle-of-the-linked-list

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想:

用C++可以用快慢指针的方法来解决,快指针一次走两步,慢指针一次走一步,这样当快指针指到了末尾的时候,慢指针就到中间结点了,直接返回慢指针指向的结点就可以了

用Java解决这个题可以直接用LinkedList,每次把cur加入到list集合中,最后直接用返回list.get(list.size() / 2)就可以了。在这里需要提及一下list.get(i)返回来的是list集合中第 i + 1个元素

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == nullptr) {
            return nullptr;
        }
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != nullptr && (fast->next) != nullptr){
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};


c59c3529a5adc1d9b22b21d36022da83_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg4ODQw,size_16,color_FFFFFF,t_70.png

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        List<ListNode>list = new LinkedList <ListNode>();
        ListNode cur = head;
        while(cur != null){
            list.add(cur);
            cur = cur.next;
        }
        return list.get(list.size()/2);
    }
}

f88474a8bf11773f27ba2abe6627c41e_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg4ODQw,size_16,color_FFFFFF,t_70.png


相关文章
|
2月前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
76 1
|
1月前
|
存储 算法 搜索推荐
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念,通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中,理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
21 1
|
3月前
链表的中间结点
链表的中间结点
182 57
|
6月前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
53 0
|
2月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
18 0
|
4月前
|
算法
LeetCode第19题删除链表的倒数第 N 个结点
该文章介绍了 LeetCode 第 19 题删除链表的倒数第 N 个结点的解法,通过使用快慢双指针,先将快指针移动 n 步,然后快慢指针一起遍历,直到快指针到达链尾,从而找到倒数第 N 个结点的前一个结点进行删除,同时总结了快慢指针可减少链表遍历次数的特点。
LeetCode第19题删除链表的倒数第 N 个结点
|
5月前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
40 1
【数据结构OJ题】链表中倒数第k个结点
|
4月前
【刷题记录】链表的中间结点
【刷题记录】链表的中间结点
|
5月前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
28 0
【数据结构OJ题】链表的中间结点
|
6月前
|
算法
19.删除链表的倒数第N个结点
19.删除链表的倒数第N个结点