【简单】在单链表中删除倒数第K个节点－Java

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.List; /** * 在单链表中删除倒数第K个节点 * * 【题目】 * 实现一个函数，删除单链表中倒数第K个节点。 * * 【要求】 * 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。 * * 【难度】 * 简单 * * 【解答】 * 本题较为简单，实现方式也是多种多样，本文提供一种方法供读者参考。 * * 如果链表为空或者K值小于1，这种情况下，参数是无效的，直接返回即可。除此之外，让链表从头开始走到尾，每移动一步，就让K的 * 值减1。 * 当链表走到结尾时，如果K值大于0，说明不用调整链表，因为链表根本没有倒数第K个节点，此时将原链表直接返回即可；如果K值等 * 于0，说明链表倒数第K个节点就是头节点，此时直接返回head.next，也就是原链表的第二个节点，让第二个节点作为链表的头返回 * 即可，相当于删除头节点；接下来，说明一下如果K值小于0，该如何处理。 * * 先明确一点，如果要删除链表的头节点之后的某个节点，实际上需要找到要删除节点的前一个节点。 * 如果K值小于0，如何找到要删除节点的前一个节点呢？方法如下： * １、重新从头节点开始走，每移动一步，就让K的值加1。 * ２、当K等于0时，移动停止，移动到的节点就是要删除节点的前一个节点。 * * 这样做是非常好理解的，因为如果链表长度为N，要删除倒数第K个节点，很明显，倒数第K个节点的前一个节点就是第N-K个节点。在 * 第一次遍历后，K的值变为K-N。第二次遍历时，K的值不断加1，加到0就停止遍历，第二次遍历当然会停到第N-K个节点的位置。 * * 具体过程请参看如下代码中的removeLastKthNode方法。 * * @author Created by LiveEveryDay */ public class RemoveLastKthNodeInSingleList { public static class Node { public int data; public Node next; public Node(int data) { this.data = data; } } public static Node removeLastKthNode(Node head, int k) { if (head == null || k < 1) { return head; } Node cur = head; while (cur != null) { k--; cur = cur.next; } if (k > 0) { } else if (k == 0) { head = head.next; } else { cur = head; while (++k != 0) { cur = cur.next; } cur.next = cur.next.next; } return head; } public static void main(String[] args) { Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); Node node5 = new Node(5); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; removeLastKthNode(node1, 4); Node n = node1; while (n != null) { System.out.printf("%d ", n.data); n = n.next; } } } // ------ Output ------ /* 1 3 4 5 */