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

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

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


目录
相关文章
|
9天前
|
算法 容器
OJ刷题日记:2、双指针(2)
OJ刷题日记:2、双指针(2)
17 0
|
1天前
|
存储 C语言
用指针处理链表
用指针处理链表
10 3
|
1天前
|
存储 C语言
链表—初始化指针变和创建新的节点------区别应用分析
链表—初始化指针变和创建新的节点------区别应用分析
|
3天前
|
存储 缓存 搜索推荐
指针链表
指针链表
11 0
|
9天前
|
算法 Java 索引
【Java 刷题记录】双指针(下)
【Java 刷题记录】双指针
29 0
|
9天前
|
算法 Java 容器
【Java 刷题记录】双指针(上)
【Java 刷题记录】双指针
22 0
|
9天前
教你三指针拿捏链表翻转
教你三指针拿捏链表翻转
|
9天前
|
算法 测试技术 容器
【刷题】双指针进阶
请看入门篇 :双指针入门
15 0
【刷题】双指针进阶
|
9天前
|
算法 测试技术 容器
【刷题】双指针入门
经过这四道题目的洗礼,我大概对双指针有了初步印象,接下来我会继续努力!!!
46 13
【刷题】双指针入门
|
9天前
|
算法 测试技术
OJ刷题日记:1、双指针(1)
OJ刷题日记:1、双指针(1)
19 0