栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java与数据结构-单链表的应用

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java与数据结构-单链表的应用

1.求单链表中有效节点的个数

public static int getLength(HeroNode head){
        HeroNode temp = head.next;//不统计头结点
        int count = 0;
        while (temp != null){
            count++;
            temp = temp.next;
        }
        return count;
    }

2.新浪面试题——寻找链表倒数第k个节点

public static int getLength(HeroNode head){
        HeroNode temp = head.next;//不统计头结点
        int count = 0;
        while (temp != null){
            count++;
            temp = temp.next;
        }
        return count;
    }
    public static HeroNode findNode(HeroNode head,int k){
        if (head.next == null)
            return null;
        int index = getLength(head)+1-k;//顺序索引
        if (index > getLength(head) || index <= 0)
            return null;
        HeroNode temp = head;
        while (index > 0){
            temp = temp.next;
            index--;
        }
        return temp;
    }

3.腾讯面试题——单链表的反转(头插法)

public static void reverseList(HeroNode head){
        if (head.next == null || head.next.next == null)
            return;
        HeroNode cur = head.next;//辅助变量,用于遍历原来的链表
        HeroNode next = null;//指向当前节点的下一节点
        HeroNode reverseHead = new HeroNode(0,"","");
        //遍历原来的链表,每遍历一个节点就将其取出,并放在新的链表的最前端
        while (cur != null){
            next = cur.next;
            cur.next = reverseHead.next;//将cur的下一节点指向新的链表的最前端
            reverseHead.next = cur;//将reverseHead和cur连接起来
            cur = next;//cur后移
        }
        head.next = reverseHead.next;
    }

4.百度面试题——从尾到头打印单链表

方式1:反向遍历,先反转再打印,但是会破坏原本链表结构,不建议。

方式2:栈,不会改变链表原本的结构

public static void reversePrint(HeroNode head){
        if (head.next ==null)
            return;
        Stack record = new Stack<>();
        HeroNode temp = head.next;
        while (temp != null){
            record.push(temp);
            temp = temp.next;
        }
        while (!record.isEmpty()){
            System.out.println(record.pop());
        }
    }

5.合并两个有序的链表,合并之后的链表依旧有序

leetcode——剑指offer25

 //递归方法
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        else if (l2 == null)
            return l1;
        else if ( l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
        else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
//迭代方法
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode preHead = new ListNode(-1);
        ListNode pre = preHead;
        while (l1 != null && l2!=null){
            if (l1.val <= l2.val){
                pre.next = l1;
                l1 = l1.next;
            }
            else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        pre.next = l1 == null ? l2:l1;
        return preHead.next;
    }

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/947196.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号