一、前言
盲目刷题只会让自己心态爆炸,所以本期14天算法学习计划,也是LeetCode上的 [算法]学习计划,在本专栏的每一篇文章都会整理每一天的题目并给出详细题解,以及知识点的整理
二、知识点
链表
链表——初识链表
快慢指针
一种双指针的特殊移动方式,一般快指针的移动步长为慢指针的两倍,通过两个指针之间的差来解决问题
三、LeetCode876. 链表的中间结点
1.题目
LeetCode876.
链表的中间结点
给定一个头结点为 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,我们返回第二个结点。
2.解题思路
本道题我们采用快慢指针的方法,由于快指针的步长是慢指针的两倍,所以当快指针到达数组未的时候,慢指针恰好移动到数组正中间,完美的解决了本题
如下图所示,第一次:快慢指针都指向0索引处,第二次:快指针向后移动两个索引、慢指针向后移动一个索引
接着也是一样,快指针每次都以步长为2向后移动,其实不难发现慢指针的值都是快指针的值的一半,所以当快指针指向数组末尾的时候,慢指针恰好指向数组中间,我们只需要返回慢指针的值即可
3.代码实现
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ 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; } }
4.复杂度分析
- 时间复杂度:O(N)
N 是给定链表中的结点数目
- 空间复杂度:O(1)
只需要常数空间存放 slow 和 fast 两个指针
5.验证代码
6.其它解法
1️⃣数组
class Solution { public ListNode middleNode(ListNode head) { ListNode[] A = new ListNode[100]; int t = 0; while (head != null) { A[t++] = head; head = head.next; } return A[t / 2]; } }
- 时间复杂度:O(N)
其中 N 是给定链表中的结点数目
- 空间复杂度:O(N)
即数组 A 用去的空间
2️⃣单指针法
class Solution { public ListNode middleNode(ListNode head) { int n = 0; ListNode cur = head; while (cur != null) { ++n; cur = cur.next; } int k = 0; cur = head; while (k < n / 2) { ++k; cur = cur.next; } return cur; } }
- 时间复杂度:O(N)
其中 N 是给定链表的结点数目
- 空间复杂度:O(1)
只需要常数空间存放变量和指针
四、结语
快慢指针问题比较复杂,所以要理解其原理所在,如果有更加简洁的解法欢迎留言评论