删除链表的中间节点和a/b处的节点-创新互联

题目1:给定链表的头节点head,实现删除链表的中间节点的函数

光泽ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:18982081108(备注:SSL证书合作)期待与您的合作!

如果链表是 1——2——3—— 4,删除2节点

如果是1——2——3——4——5,删除3节点

思路:

快慢指针,让pre指针指向头节点,cur指针指向第三个节点:

例如 1 2 3 4 5 6

pre是1 ,cur是3,当cur后面还有两个节点的时候,pre走一步,cur走两步。走完之后,pre是2,cur是5。然后pre就是要删除节点的前一个节点。

代码实现:

public static Node removeMidNode(Node head){
        //如果链表为空 或者长度为1 直接返回
        if (head == null || head.next == null) {
            return head;
        }
        //如果链表长度为2 ,删除头节点
        if (head.next.next == null) {
            return head.next;
        }
        //第一个节点 和 第三个节点
        Node pre = head;
        Node cur = head.next.next;
        //快慢指针
        // 1 2 3 4 5 6 ,pre是1  cur是3
        while(cur.next != null && cur.next.next != null) {
            pre = pre.next;
            cur = cur.next.next;
        }
        pre.next = pre.next.next;
        return head;
    }

题目2:给定链表头节点head,整数a,b,删除位于a/b处节点的函数

思路:

链表长度为n,删除a/b处的节点,也就是 (a*n)/ b 向上取整的节点。

确定了要删除的节点位置n之后,分两种情况,一种是n==1,一种是n>1

n>1时候,让cur回到头节点,n--,n减到值为1的时候,cur就走到了要删除节点的前一个节点。

public static Node removeABNode(Node head, int a , int b){
        if (a< 1 || a >b) {
            return head;
        }
        int n = 0;
        Node cur = head;
        //获取链表长度n
        while (cur != null) {
            cur = cur.next;
            n++;
        }
        n = (int)Math.ceil(((double)(a * n)) / (double)b);
        //n==1时删除头节点
        if (n == 1) {
            head = head.next;
        }
        //找到n节点前一个节点 链表是 1 2 3 4 5 6 7 
//比如现在n是 4 那么要找到3节点 ,让cur回到头节点,n--,n==1的时候,cur就走到了3节点
        if (n >1) {
            cur = head;
            while (--n != 1) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        return head;
    }

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章题目:删除链表的中间节点和a/b处的节点-创新互联
转载注明:http://scyanting.com/article/ccpjep.html