链表相关算法

package com.appdemo;

import android.util.Log;

import java.util.Stack;

public class Node {


    int value;//节点内容
    Node next;//下一个节点

    public Node(int value) {
        this.value = value;
    }

打印链表

    public void show() {//输出所有节点
        Node currentNode = this;
        while (true) {
            Log.w("TAG", "---all---" + currentNode.value);
            //取出下一个节点
            currentNode = currentNode.next;
            //如果是最后一个节点
            if (currentNode == null) {
                break;
            }
        }
    }

判断链表是否有环形

首先创建两个指针1和2,同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。
在一个环形跑道上,两个运动员在同一地点起跑,一个运动员速度快,一个运动员速度慢。当两人跑了一段时间,速度快的运动员必然会从速度慢的运动员身后再次追上并超过,原因很简单,因为跑道是环形的。

private void loop() {
    // 构造链表 1->2->3->4->5->6-4;
    Node a = new Node(1);
    Node b = new Node(2);
    Node c = new Node(3);
    Node d = new Node(4);
    Node e = new Node(5);
    Node f = new Node(6);
    a.next = b;   b.next = c;   c.next = d;
    d.next = e;
    e.next = f;
    //f.next = d;//构造环形  4    // a.show();//输出所有节点
     Log.w("TAG", "----" + isLoop(a));
}
public static boolean isLoop(Node head){
    Node slow = head.next;
    Node fast = head.next.next;
    // 链表为空或者只有一个节点
    if(slow == null || fast == null){
        return false;
    }
    while(slow.next != null){
        // 只有 两个节点,当然是不存在循环的
        if(fast.next == null){
            return false;
        }
        // 如果slow的数据域和fast的数据域相同,则表示有环
        if(slow.value == fast.value){
            return true;
        }
        // slow指针走一步,fast走两步
        slow = slow.next;
        fast = fast.next.next;
        //如果fast走到最后为空,表示没有环
        if(fast == null){
            return false;
        }
    }
    return false;
}

反转链表 递归

    public Node reverse(Node head) {
        //如果链表为空或者链表中只有一个元素
        if (head == null || head.next == null) {
            return head;
        }
        Node temp = head.next;
        ////先反转后面的链表,走到链表的末端结点
        Node newHead = reverse(head.next);
        //再将当前节点设置为后面节点的后续节点
        temp.next = head;
        head.next = null;
        return newHead;
    }

    /**
     * 1->2->3->4  原始链表
     * 1,从第二个数据开始,间第二个的指针指向第一个,比喻2->1
     * 2,将现有的头部  1转换成尾部,尾部的next为null
     * 3,将从第二个node开始,循环next指向前一个
     * 4,一直有个指针指向还没有反转的链表的头部
     * 需要左中右三个指针
     */
    public static Node reverseList(Node node) {
        Node pre = null;
        Node next = null;
        while (node != null) {
            next = node.next; //第二个节点
            node.next = pre;//2 null
            pre = node;//baocun  1 jiedian
            node = next;
            pre.show();//输出所有节点
            Log.w("TAG", "----------------");
        }
        return pre;
    }

删除某一个节点

    public void removeNode() {
        //通过当前节点找到下下一个节点
        Node newNext = next.next;
        //再把下一个节点赋值给当前节点的下一个节点
        this.next = newNext;
    }

插入某个节点,作为当前节点的下一个节点

    public void addNode(Node node) {
        //取出下一个节点,作为下下个节点
        Node nextNode = next;
        //把新节点作为单点节点的下一个节点
        this.next = node;
        //把下下个节点作为设置新节点的下一个节点
        node.next = nextNode;
    }

合并两个有序链表

    public Node Merge(Node list1, Node list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        Node pMergeHead = null;
        if (list1.value < list2.value) {
            pMergeHead = list1;
            pMergeHead.next = Merge(list1.next, list2);
        } else {
            pMergeHead = list2;
            pMergeHead.next = Merge(list1, list2.next);
        }
        return pMergeHead;
    }

输入一个链表,输出该链表中倒数第k个结点。

    public Node FindKthToTail(Node head, int k) {
        Node pre = null, p = null;
        //两个指针都指向头结点
        p = head;
        pre = head;
        //记录k值
        int a = k;
        //记录节点的个数
        int count = 0;
        //p指针先跑,并且记录节点数,当p指针跑了k-1个节点后,pre指针开始跑,
        //当p指针跑到最后时,pre所指指针就是倒数第k个节点
        while (p != null) {
            p = p.next;
            count++;
            if (k < 1) {
                pre = pre.next;
            }
            k--;
        }
        //如果节点个数小于所求的倒数第k个节点,则返回空
        if (count < a) return null;
        return pre;
    }

两个栈实现一个队列

    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();

        public void push(int node) {
            stack1.push(node);
        }

        public int pop() {
            if (stack1.empty() && stack2.empty()) {
                throw new RuntimeException("Queue is empty!");
            }
            if (stack2.empty()) {
                while (!stack1.empty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,681评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,710评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,623评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,202评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,232评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,368评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,795评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,461评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,647评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,476评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,525评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,226评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,785评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,857评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,090评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,647评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,215评论 2 341

推荐阅读更多精彩内容

  • 漫画算法:如何判断链表有环? - 文章 - 伯乐在线 大四毕业前夕,计算机学院, 正在四处求职的小灰碰到了同系的学...
    viva158阅读 1,248评论 1 2
  • 搞懂单链表常见面试题 Hello 继上次的 搞懂基本排序算法,这个一星期,我总结了,我所学习和思考的单链表基础知识...
    醒着的码者阅读 4,570评论 1 45
  • 2019 iOS面试题大全---全方面剖析面试2018 iOS面试题---算法相关1、七种常见的数组排序算法整理(...
    Theendisthebegi阅读 11,797评论 7 14
  • 好多人都说说话是一门艺术,你是否精于这门艺术,要看你对这门艺术的“拿捏”是否娴熟。要是说到这,那我认为和说话...
    酒言之阅读 446评论 0 0
  • 部分内容尚未迁移过来,发帖占位。我们根据开课需要,不断从WORD、PPT、小视频、书籍、讲义等传统课件形式,向公共...
    张老师大语文阅读 378评论 0 0