数据结构--链表刷题(一)快慢指针(上)

简介: 数据结构--链表刷题(一)快慢指针

1.快慢指针

 先看一道简单的题目:返回中间结点

这道题有一个最朴素的做法就是先遍历一边链表,设置计数器求出链表长度,再重新走1/2的链表长度,即可返回中间节点

        // 第二种解法  
        //这种解法需要遍历两次链表
        ListNode cur1 = head;
        int cnt = 0;
 
        while(cur1 != null) {
            cnt++;
            cur1 = cur1.next;
        }
 
        ListNode cur2 = head;
        cnt = cnt/2;
        while(cnt != 0) {
            cur2 = cur2.next;
            cnt--;
        }
 
        return cur2;

 但是这种方式有个明显的缺陷,就是你实际上是遍历了两遍链表,那有没有只遍历一次链表就能获得中间结点的方法呢?答案是有的,利用快慢指针

// 第一种解法  只需遍历一次链表
        ListNode slow = head,fast = head;
 
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
 
        return slow;

快慢指针的核心思想其实是一种数学问题,即在相同时间内,路程之比就是速度之比

「力扣」第 19 题: 倒数第 k 个结点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 使用虚拟头节点 -- 能更好的处理删除头节点的问题
        ListNode dummyhead = new ListNode(0);
        dummyhead.next = head;
 
        ListNode slow = dummyhead;
        ListNode fast = dummyhead;
 
        while(n > 0) {
            fast = fast.next;
            n--;
        }
 
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyhead.next;
    }
}

一个小细节:如果不使用虚拟头节点  在删除头节点的过程中会出错

数据结构--链表刷题(一)快慢指针(下)https://developer.aliyun.com/article/1480782?spm=a2c6h.13148508.setting.15.361f4f0eyTL4lb


目录
相关文章
|
17天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
44 4
|
18天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
18天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
21天前
|
算法 索引
单链表题+数组题(快慢指针和左右指针)
单链表题+数组题(快慢指针和左右指针)
26 1
|
1月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
1月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
23 3
|
1月前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
16 0
数据结构与算法学习五:双链表的增、删、改、查
|
17天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
38 0
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
|
1月前
|
存储 Java
【数据结构】链表
【数据结构】链表
18 1