当前位置：
  1. 首页
  2. 链表专题
  3. 正文

链表训练1：删除单链表的第K个节点

链表专题 0 865

题目描述

在单链表中删除倒数第 K 个节点

要求

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

解答

删除的时候会出现三种情况：

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

2、倒数第 K 个节点就是第一个节点

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

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

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

如果 num == K，则属于第二中情况。

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

代码如下：

//定义节点
class Node{
    public int value;
    public Node next;
    public Node(int data) {
        this.value = data;
    }
}

public class 删除倒数第K个节点 {
    public Node removeLastKthNode(Node head, int K) {
        if(head == null || K < 1)
            return head;
        Node temp = head;
        int num = 0;
        while (temp != null) {
            num++;
            temp = temp.next;
        }
        if (num == K) {
            return head.next;
        }
        if (num > K) {
            temp = head;
            //删除第(num-k+1)个节点
            //定位到这个点的前驱
            while (num - K - 1 != 0) {
                temp = temp.next;
                num--;
            }
            temp.next = temp.next.next;
        }
        return head;
    }
}

对于这种链表题，思路其实很简单，但如果让你来写代码，你不一定就能写对，所以呢，大家切勿眼高手低，一定要自己实现一遍，并且这道题，也属于面试中的高频题。

如果你能提供其他代码版本，欢迎评论区给出哈。

如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人，帅地正在疯狂更新中….

上一篇 链表专题简介
下一篇 链表训练2：删除单链表的中间节点

发表评论

后才能评论

评论(6)