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

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

如果链表是 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元起，快前往官网查看详情吧