资讯专栏INFORMATION COLUMN

单链表的操作 Java

bergwhite / 1523人阅读

摘要:单链表的反转头插法两个指针,表示的后一个节点,表示的前一个节点,都作为临时节点先把节点指向后面节点的指针保存起来,则此时节点和节点值和指针是相同的指向前一个节点与进行右移,递归斜体文字链表的倒数第个节点双指针解决先走步,然后开始走,走到结尾

单链表的反转

头插法
两个指针,next 表示 head 的后一个节点,pre 表示 head 的前一个节点,都作为临时节点
先把 head 节点指向后面节点的指针保存起来 next = head.next ,则此时 next 节点和 2 节点值和指针是相同的
head 指向前一个节点 head.next = pre
pre 与 head 进行右移 pre = head,head = next

public static ListNode ReverseList(ListNode head) {
    ListNode pre = null;
    ListNode next = null;
    if (head == null || head.next == null){
        return head;
    }
    while (head != null){
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}
递归
*斜体文字*public static ListNode ReverseListStack(ListNode head){
    if (head == null || head.next == null){
        return head;
    }
    ListNode node = ReverseListStack(head.next);
    head.next.next = head;
    head.next = null;
    return node;
}

链表的倒数第 K 个节点

1.双指针解决
2.fast 先走K步,然后 low 开始走,fast 走到结尾的时候 low 则指向倒数第 K 个节点
3.主要 异常情况,K < 0 ,K > len(List)

public static ListNode getKNode(ListNode head,int k){
    if (head == null || k < 0){
        return null;
    }
    ListNode pre = head;
    ListNode next = head;
    for (int l = 0; l < k; l++) {
        if (next != null) {
            next = next.next;
        }else {
            return null;
        }
    }
    while (next != null){
        pre = pre.next;
        next = next.next;
    }
    return pre;
}

链表是否有环、环的入口

1.快慢指针,快指针每次走两步,慢指针每次走一步
2.若在遍历链表的过程中,出现 快指针指向的节点等于慢指针指向的节点,说明链表有环,并且相遇的点一定在环中(不然不可能相遇)
3.设定 链表头到环入口的距离为 x ,环入口到相遇点的距离为 a,环的总长度为 c,环相遇点到入口的距离为 b,则 a+b = c
4.假设此时快慢指针在环内相遇,那么
慢指针走过的距离 Step(low) = x + m * c + a (m为慢指针走过的圈数) ①
快指针走过的距离 Step(fast) = x + n * c + a (n为快指针走过的圈数) ②
Step(fast) = 2 * Step(low)③
5.根据①②③,得到 x = c (n - 2 m - 1)+ b ,也就是说链表头到环入口的距离 x 等于 环的长度 c 的倍数 + b
6.相遇时,此时若将慢(快)其中一个放到链表开头,然后开头的指针和环中的指针一起一步步走,那么开头的指针走 x 步时,环中的指针将走 k 圈 + b 步,此时 两指针再次相遇,并且相遇点位环入口点,即为所求

public static ListNode getCircleroot(ListNode head){
    if (head == null || head.next == null){
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast){
            // 相遇时 终止循环
            break;
        }
    }
    if (fast != slow){
        return null;
    }
    fast = head;  // 将其中一个指针指向开头
    while (fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    // 再次相遇时即为环入口点
    return fast;
}

欢迎加入学习交流群569772982,大家一起学习交流。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/70521.html

相关文章

  • 【数据结构】Java语言描述-单链表的基本操作

    摘要:单链表是数据结构中以动态结构存储的线性结构,在语言中,一般用本类对象引用的方式在内存中将一组相同类型的对象存储,熟悉单链表的基本操作有助于灵活解决此类算法问题。 单链表是数据结构中以动态结构存储的线性结构,在Java语言中,一般用本类对象引用的方式在内存中将一组相同类型的对象存储,熟悉单链表的基本操作有助于灵活解决此类算法问题。 1.单链表中的节点可以用节点类型描述如下: public...

    sevi_stuo 评论0 收藏0
  • 自己动手写一个单链

    摘要:链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。三单向链表的实现下面的程序分别实现了线性表的初始化获取线性表长度获取指定索引处元素根据值查找插入删除清空等操作。 文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号:好好学java,获取优质学习资源。 一、概述 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读...

    岳光 评论0 收藏0

发表评论

0条评论

bergwhite

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<