• 数据结构与算法-单链表中删除倒数第 K 个节点的算法
  • 发布于 2个月前
  • 188 热度
    0 评论
  • 赵英杰
  • 1 粉丝 17 篇博客
  •   
以专题的形式更新刷题贴,欢迎跟我一起学习刷题。每道题会提供简单的解答。

【题目描述】
在单链表中删除倒数第 K 个节点。
【要求】
如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)

【难度】

【解答】

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

1、不存在倒数第 K 个节点,此时不用删除。
2、倒数第 K 个节点就是第一个节点。
3、倒数第 K 个节点在第一个节点之后。
所以我们可以用一个变量 num 记录链表一共有多少个节点。
如果 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;
   }
}

//删除第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 != 0) {
               temp = temp.next;
               num--;
           }
           temp.next = temp.next.next;
       }
       return head;
   }

用户评论