Markdown编辑器 golang plugins module mtu原理 scripting sas vue全局组件 字符串中包含某个字符串 maya曲线建模 matlab取实部 python函数大全 javasubstring java入门级教程 java框架 java获取当前月 java日期函数 linux系统安装教程图解 php项目实例 摩斯密码翻译 在线pr序列设置 圆形截图 两表关联查询 网络文件服务器 福昕阅读器绿色版 php四舍五入 苹果放大镜 idea导出jar包 go程序设计语言 淘宝图片下载 maven项目打包 挑战程序设计竞赛 ug拔模 oracle表分区 cinema4d下载 qq农场图标 燃烧之血十字架 alert换行 捷速pdf编辑器 ps怎么做漂亮艺术字
当前位置: 首页 > 学习教程  > 编程语言

Leetcode 876: Middle of the Linked List (Python)

2021/1/28 23:22:18 文章标签:

文章目录题目描述题目分析代码实现日期题目描述 Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node. Example 1: Input: [1,2,3,4,5] Output: Node 3 from …

文章目录

    • 题目描述
    • 题目分析
    • 代码实现
    • 日期

题目描述

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3. (The judge’s serialization of this node is [3,4,5]).Note that we returned a Lis Node object ans, such that:ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

题目分析

分类上是单链表的题目,需要我们返回中间的node,因为是链表所以会把后面的数都带上。这里的思路是用两个指针,一个慢指针,一个快指针。

慢指针的速度为1,快指针的速度为2.

在移动了n次之后,慢指针的位置是 1 + n,快指针的位置是 1+ 2n。

当Linked List里的数字是奇数个时,快指针会运行到最后一个数字,其中点是 ( 1 + 2 n ) + 1 2 = 1 + n \frac{(1+2n)+1}{2}=1+n 2(1+2n)+1=1+n

当Linked List里的数字是偶数个时,快指针会运行到最后一个数字之后的 Null, 题中想要的两个中点之后的那个也是这么计算的 ( 1 + 2 n ) − 1 2 + 1 = n + 1 \frac{(1+2n)-1}{2}+1= n+1 2(1+2n)1+1=n+1

代码实现

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = head 
        fast = head 
        
        while fast and fast.next: # 如果没有fast.next, 偶数个的情况下fast指针指到Null时
        						  #	还会再移动两个指针一次
            slow = slow.next 
            fast = fast.next.next 
        
        return slow 

日期

2021-1-28 #876 第一种方法


本文链接: http://www.dtmao.cc/news_show_650194.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?