文档章节

2.链表

o
 osc_73pstnki
发布于 07/04 11:24
字数 937
阅读 26
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

点击使用幕布网页版查看(含思维导图)

链表(单链表)是一种通过指针将一组零散的内存块串联起来的数据结构,每个链表的结点除了存储的数据之外,还需要记录链上的下一个节点的地址

  • 链表的插入和删除(给定节点指针)时间复杂度O(1),但遍历删除的时间复杂度是O(n)

  • 双向链表:每个结点不止有一个后继指针指向后面的结点,还有一个前驱指针指向前面的结点。在删除指定指针指向的节点时,时间复杂度仅为O(1)若链表是有序链表,那么查找时可以向前向后遍历,平均能少遍历一半的数据

  • 链表有关算法

    • 单链表反转
      定义两个节点curr,pre。curr.next指向pre,然后curr、pre后移一位,重复直到最后一个节点。​

    • 检测环
      1.快慢指针,快指针每次走两步,慢指针每次走一步。​相遇则说明有环
      2.遍历链表并将节点值加入散列表中,若有重复的说明有环​

    • 有序链表合并
      定义一个哨兵,每次加入较小节点,最后加入较长链表剩余部分

    • 删除倒数第k个节点
      定义快慢指针,从头节点开始快指针先走k-1步,然后快慢同时走,快指针走到表尾时慢指针指向的就是倒数第k个

    • 求中间节点
      快慢指针,快指针每次两步慢指针每次一步,快指针走到表尾慢指针指向中间节点

    • 判断回文
      快慢指针找到中点,慢指针移动过程中同时反转链表,然后从中点至两端一起移动并判断

链表Java实现


public class myLinkedlist {
    public Node head;

    public myLinkedlist() {
        head = new Node(-1);
    }

    /**
     * 将data加到链表尾部
     *
     * @param data
     * @return
     */
    public boolean append(int data) {
        Node iter = head;
        while (iter.next != null) iter = iter.next;
        iter.next = new Node(data);
        return true;
    }

    /**
     * 将value插入到index之后
     *
     * @param index
     * @return
     */
    public boolean insertAfter(int index, int value) {
        Node iter = head;
        while (iter.data != index && iter.next != null) iter = iter.next;
        if (iter.data != index && iter.next == null) {
            System.out.println("链表中无对应节点!");
            return false;
        }

        Node temp = iter.next;
        iter.next = new Node(value);
        iter.next.next = temp;

        return true;
    }

    public boolean delete(int index) {
        Node iter = head;
        while (iter.next != null && iter.next.data != index) iter = iter.next;
        if (iter.data != index && iter.next == null) {
            System.out.println("链表中无对应节点!");
            return false;
        }
        Node temp = iter.next.next;
        iter.next = temp;
        return true;
    }

    /**
     * 反转链表
     */
    public void reverse() {
        Node iter = head.next;

        if (iter.next == null)
            return;

        Node pre = iter;
        Node mid = iter.next;
        Node after = mid.next;
        pre.next = null;

        //after为null时说明mid是最后一个
        while (after != null) {
            //每次将mid指向pre
            mid.next = pre;
            pre = mid;
            mid = after;
            after = after.next;
        }
        mid.next = pre;
        head.next = mid;
    }

    public boolean isPalindrome() {
        if (head.next == null) {
            System.out.println("链表为空!");
            return false;
        }
        //只有两个节点
        if (head.next.next.next == null) {
            int first = head.next.data;
            int second = head.next.next.data;
            if (first == second)
                return true;
            else
                return false;
        }
        Node fast;//快指针
        Node slow;//慢指针
        fast = slow = head.next;
        int fStep;//快指针步数
        int sStep;//慢指针步数
        fStep = sStep = 0;
        while (fast.next != null) {
            fast = fast.next;
            fStep++;
        }
        sStep = fStep / 2;

        //慢指针向前移动,同时将单链表反转
        Node pre, mid, after;
        pre = slow;
        mid = slow.next;
        after = mid.next;

        slow.next = null;

        while (sStep > 0) {
            mid.next = pre;
            pre = mid;
            mid = after;
            after = after.next;
            sStep--;
        }

        Node toStart, toEnd;
        //奇数遍历起点
        if (fStep % 2 == 1) {
            toStart = pre;
            toEnd = mid;
        }
        //偶数遍历起点
        else {
            toStart = pre.next;
            toEnd = mid;
        }

        do {
            if (toStart.data != toEnd.data)
                return false;
            toStart = toStart.next;
            toEnd = toEnd.next;
        } while (toStart != null && toEnd != null);
        return true;
    }

    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node iter = head;
        int size = 0;
        while (iter.next != null) {
            builder.append(iter.next.data + ",");
            size ++;
            iter = iter.next;
        }
        return builder.toString() + "\t(size: " + size + ")";
    }

    public void linkedlistTest(){
        myLinkedlist test = new myLinkedlist();
        test.append(1);
        System.out.println(test.toString());
        test.delete(1);
        System.out.println(test.toString());
        test.append(2);
        System.out.println(test.toString());
        test.insertAfter(1,3);
        System.out.println(test.toString());
        test.delete(2);
        System.out.println(test.toString());
        test.append(4);
        test.append(5);
        test.append(6);
        System.out.println(test.toString());
        test.reverse();
        System.out.println(test.toString());
        test.reverse();
        System.out.println(test.toString());
        //测试是否为回文串
        test.append(1);
        test.append(2);
        test.append(3);
        test.append(2);
        test.append(1);
        System.out.println(test.isPalindrome());
    }


}

class Node {
    int data;
    Node next;

    protected Node(int data) {
        this.data = data;
        this.next = null;
    }
}
o
粉丝 0
博文 75
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Netty那点事(三)Channel与Pipeline

Channel是理解和使用Netty的核心。Channel的涉及内容较多,这里我使用由浅入深的介绍方法。在这篇文章中,我们主要介绍Channel部分中Pipeline实现机制。为了避免枯燥,借用一下《盗梦空间》的...

黄亿华
2013/11/24
2W
22
硬实时操作系统--Raw OS

Raw-OS 起飞于2012年,Raw-OS志在制作中国人自己的最优秀硬实时操作系统。 Raw-OS 操作系统特性 内核最大关中断时间无限接近0us, s3c2440系统最大关中断时间实测0.8us。 支持idle任务级别的事...

jorya_txj
2013/03/19
6.3K
1
SmartGWT学习整理 2、理解核心中的核心DataSource

SmartGWT学习整理 2、理解核心中的核心DataSource DataSource之所以重要,是因为它负责所有的与服务器的数据交互,几乎所有的控件都离不开它。 可以这样说,理解了DataSource就掌握了SmartGW...

st97
2010/11/16
2K
2
JCF框架源码分析系列-ArrayList(二)

1、揭开ArrayList真面目 作者将在本文详细赘述日常开发中最常用集合类-ArrayList,本次JCF源码分析基于JDK1.7,主要从以下几个方向分析: UML类图关系 数据结构 接口介绍 常用、重要方法的实...

Ambitor
2015/11/30
385
0
用 VIPER 构建 iOS 应用架构(2)

【编者按】本篇文章由 Jeff Gilbert 和 Conrad Stoll 共同编写,通过构建一个基础示例应用,深入了解 VIPER,并从视图、交互器等多个部件理清 VIPER 的整体布局及思路。通过 VIPER 构建 iOS ...

OneAPM蓝海讯通
2015/08/07
289
0

没有更多内容

加载失败,请刷新页面

加载更多

Subversion存储库中“分支”,“标记”和“主干”的含义是什么?

问题: I've seen these words a lot around Subversion (and I guess general repository) discussions. 我已经在Subversion(我猜通用存储库)讨论中看到了很多这样的话。 I have been us......

富含淀粉
今天
5
0
《Java8实战》笔记(03):Lambda表达式

本文源码 Lambda 管中窥豹 可以把Lambda表达式理解为简洁地表示可传递的匿名函数的一种方式:它没有名称,但它有参数列表、函数主体、返回类型,可能还有一个可以抛出的异常列表。 Lambda表达...

巨輪
今天
7
0
从其他文件夹导入文件 - Importing files from different folder

问题: I have the following folder structure. 我有以下文件夹结构。 application/app/folder/file.py and I want to import some functions from file.py in another Python file which r......

javail
今天
22
0
大数据研发学习之路--Hadoop集群搭建

阅读编译文档 准备一个hadoop源码包,我选择的hadoop版本是:hadoop-2.7.7-src.tar.gz,在hadoop-2.7.7的源码 包的根目录下有一个文档叫做BUILDING.txt,这其中说明了编译hadoop所需要的一些...

DSJ-shitou
今天
8
0
OSChina 周五乱弹 —— 特么是别的公司派来的特洛伊木马吧?

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 小小编辑推荐:《我会守在这里》- 毛不易 《我会守在这里》- 毛不易 手机党少年们想听歌,请使劲儿戳(这里) @FalconChen :股市连跪了五天,...

小小编辑
今天
77
2

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部