14天刷爆LeetCode算法学习计划——Day05 快慢指针(1)

简介: 14天刷爆LeetCode算法学习计划——Day05 快慢指针(1)

一、前言


盲目刷题只会让自己心态爆炸,所以本期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索引处,第二次:快指针向后移动两个索引、慢指针向后移动一个索引


053297e4a4054dd8a2e595da619930e7.png


接着也是一样,快指针每次都以步长为2向后移动,其实不难发现慢指针的值都是快指针的值的一半,所以当快指针指向数组末尾的时候,慢指针恰好指向数组中间,我们只需要返回慢指针的值即可


428e6db4f6f1455a9b1beeaf98270d1f.png


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.验证代码


f0174595595b4f54b95e521b274185ae.png


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)

只需要常数空间存放变量和指针


四、结语


快慢指针问题比较复杂,所以要理解其原理所在,如果有更加简洁的解法欢迎留言评论

相关文章
|
22天前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
9天前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
17 2
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
49 6
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
46 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
47 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
74 0
|
3月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
38 0
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
51 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
30 0
|
3月前
|
算法 Java 索引
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
34 0