前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >初级算法(2)-链表

初级算法(2)-链表

作者头像
方丈的寺院
发布2019-08-05 17:31:20
2680
发布2019-08-05 17:31:20
举报
文章被收录于专栏:方丈的寺院方丈的寺院

链表的删除

表的删除就是指针的移动,将待删除节点的指针移动到下一个节点 题1:删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。 虽然我们并不知道,这个节点的前一个节点时什么,但是我们知道这个节点的下一个节点是什么, 将当前要删除的节点替换为下一个节点即可

代码语言:javascript
复制
public static void deleteNode(ListNode node) {
        if(node == null || node.next == null){
            return;
        }
        ListNode next = node.next;
        node.val = next.val;
        node.next = next.next;
    }

链表的反转

题:反转一个单链表 链表的反转不需要不需要创建新的对象,整个过程也就是指针的移动

  1. 首先构建一个新的节点,将头结点与原来节点分离,然后重复前一个动作,将第二个节点从原来的节点分离,并加上新的节点上
代码语言:javascript
复制
if(head == null || head.next == null) {
            return head;
        }
        // 新的节点
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            // 首先保存待移动节点的下一个节点
            next = head.next;
            // 分离当前节点,并指向新的节点
            head.next = pre;
            // 挪动新节点的指针
            pre = head;
            // 挪动旧节点指针
            head = next;
        }
        return pre;

链表的合并

题:两个有序链表的合并 有序链表的合并,就是将另外一个链表的节点不断插入另一个节点

代码语言:javascript
复制
if(l1 == null || l2 ==null) {
            return l1 == null ? l2 : l1;
        }
        ListNode head = l1.val < l2.val ? l1 : l2;
        ListNode cur1 = head == l1 ? l1 : l2;
        ListNode cur2 = head == l1 ? l2 : l1;
        ListNode pre = null ;
        ListNode next = null;
        while(!(cur1 == null || cur2 == null)) {
            // 值比另外一个节点小,就直接遍历下一个节点
            if (cur1.val <= cur2.val) {
                pre = cur1;
                cur1 = cur1.next;
            } else {
                // 将cur2的节点插入到cur1中
                next = cur2.next;
                pre.next = cur2;
                cur2.next = cur1;
                pre = cur2;
                cur2 = next;
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;

环形链表判断

代码语言:javascript
复制
if (head == null || head.next == null || head.next.next == null) {
            return false;
        }
        ListNode step1 = head;
        ListNode step2 = head;
        while (step2 != null && step2.next !=null) {
            step1 = step1.next;
            step2 = step2.next.next;
            if (step1 == step2) {
                return true;
            }
        }
        return false;

官方解答: https://leetcode-cn.com/articles/linked-list-cycle/

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-08-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 方丈的寺院 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 链表的删除
  • 链表的反转
  • 链表的合并
  • 环形链表判断
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档