网站管理助手4.0 mysql,河北建设执业信息网站,1688货源网一件代发玩具,用来做调查问卷的网站目录
LeetCode之路——876. 链表的中间结点
分析#xff1a;
解法一#xff1a;常规思路
解法二#xff1a;快慢指针 LeetCode之路——876. 链表的中间结点
给你单链表的头结点 head #xff0c;请你找出并返回链表的中间结点。
如果有两个中间结点#xff0c;则返回…目录
LeetCode之路——876. 链表的中间结点
分析
解法一常规思路
解法二快慢指针 LeetCode之路——876. 链表的中间结点
给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点。 示例 1 输入head [1,2,3,4,5]
输出[3,4,5]
解释链表只有一个中间结点值为 3 。
示例 2 输入head [1,2,3,4,5,6]
输出[4,5,6]
解释该链表有两个中间结点值分别为 3 和 4 返回第二个结点。 提示 链表的结点数范围是 [1, 100] 1 Node.val 100 分析
解法一常规思路
遍历链表利用数组存放对应节点遍历结束返回中间节点。
class Solution {public ListNode middleNode(ListNode head) {ListNode[] nodes new ListNode[100];int index 0;while (head ! null) {nodes[index] head;head head.next;}return nodes[index / 2];}
} 时间复杂度O(N) 空间复杂度O(N)
解法二快慢指针
快指针是慢指针的2倍。快指针在末尾的时候慢指针指向的节点就是要返回的。
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;}
} 时间复杂度O(N) 空间复杂度O(1)
