【链表】打卡3：删除单链表中顺数、倒数第K个结点

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题。每道题会提供简单的解答。

【题目描述】

在单链表中删除顺数、倒数第 K 个结点。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)

【难度】

士：★☆☆☆

解答

删除倒数第K个结点的时候会出现三种情况：

1、不存在倒数第 K 个结点，此时不用删除。

2、倒数第 K 个结点就是第一个结点。

3、倒数第 K 个结点在第一个结点之后。

所以我们可以用一个变量 length记录链表一共有多少个结点。

如果 length< K，则属于第一种情况。

如果 length== K，则属于第二种情况。

如果 length> K, 则属于第三种情况，此时删除倒数第 K 个结点等价于删除第 (length- k + 1) 个结点。

删除顺数第K个代码如下：

//删除单链表中的第K个结点
public static Node deleteKthNode(Node head,int K){
    if(head == null || K < 1){
        return null;
    }
    int length = 0;//链表的长度
    Node node = head;
    while(node!=null){
        length++;
        node = node.next;
    }
    if(length < K){
        return head;
    }
    node = head;
    //删除第一个
    if(K == 1){
        node = node.next;
        return node;
    }
    int i = 0;
    while(++i != K - 1){
        node = node.next;
    }
    //删除最后一个
    if(length == K){
        node.next = null;
        //node和head引用的是一个对象，所以返回head
        return head;
    }
    if(length > K){
        node.next = node.next.next;
        return head;
    }
    return null;
}

删除倒数第K个代码如下：

//删除倒数第K个结点
public static Node deleteLastKthNode(Node head, int K) {
    if(head == null || K < 1)
        return head;
    Node node = head;
    int length = 0;
    while (node != null) {
        length++;
        node = node.next;
    }
    if (length == K) {
        return head.next;
    }
    if (length > K) {
        node = head;
        //删除第(num+1-k)个结点
        //定位到这个点的前继
        //只能循环length-K次，原解这里有误，多循环了一次。原解为length-K
        while (length - K -1 != 0) { 
            node = node.next;
            length--;
        }
        node.next = node.next.next;
    }
    return head;
}

测试代码

public static void main(String[] args) {
    int i = 1;
    Node head = new Node(i);
    Node node = head;
    while(++i<6){
        node.next = new Node(i);
        node = node.next;
    }
    //node = deleteKthNode(head,3);
    node = deleteLastKthNode(head, 2);
    while(node!=null){
        System.out.println(node.value);
        node = node.next;
    }
}

来源：苦逼的码农（ID:di201805）

（完）