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

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

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


目录
相关文章
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
4天前
|
算法 索引
单链表题+数组题(快慢指针和左右指针)
单链表题+数组题(快慢指针和左右指针)
9 1
|
21天前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
23 7
|
21天前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
20 3
|
20天前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
14 0
数据结构与算法学习五:双链表的增、删、改、查
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
|
25天前
|
存储 Java
【数据结构】链表
【数据结构】链表
15 1
|
25天前
|
存储 缓存
数据结构3——双向链表
数据结构3——双向链表
91 1
|
14天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
16 0

热门文章

最新文章