文章目录
前言
算法作为极其重要的一点，是大学生毕业找工作的核心竞争力，所以为了不落后与人，开始刷力扣算法题！
第一遍，不求最优解，但求能过！！！
📢 ：❤布小禅❤
📢 作者专栏：
这是我刷第 14/100 道力扣简单题
一、题目描述
给定一个头结点为 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 之间。
二、题目解析
- 遍历链表
开辟列表/数组空间
遍历链表
将节点添加进列表/数组
返回数组长度//2的元素 - 单指针法
因为链表没有长度，也无法通过下标取值
所以定义一个指针记录长度
然后遍历链表，每次遍历让指针+1
然后再次遍历
遍历到长度//2的时候停止 - 双指针法
第二个方法有点麻烦，需要遍历两次链表
两个指针，一个跟随链表
一个以二倍速度遍历
然后以而被指针为条件结束循环
返回链表节点
三、代码
- 暴力解法
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def middleNode(self, head: ListNode) -> ListNode: li = [] while head: li.append(head) head = head.next return li[len(li)//2]
- 单指针
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def middleNode(self, head: ListNode) -> ListNode: a = head # 找个变量记录头结点，用于两次循环使用 i = 0 j = 0 while a: i += 1 a = a.next while j < i//2: j += 1 head = head.next return head
- 双指针
class Solution: def middleNode(self, head: ListNode) -> ListNode: ans = head # 答案节点 while head and head.next: ans = ans.next head = head.next.next return ans
结语
坚持最重要，每日一题必不可少！
