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

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

package live.every.day.ProgrammingDesign.CodingInterviewGuide.List; /** * 在双链表中删除倒数第K个节点 * * 【题目】 * 实现一个函数，删除双链表中倒数第K个节点。 * * 【要求】 * 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。 * * 【难度】 * 简单 * * 【解答】 * 对于双链表的调整，几乎与单链表的处理方式一样，注意last指针的重连即可。 * 具体过程请参看如下代码中的removeLastKthNode方法。 * * @author Created by LiveEveryDay */ public class RemoveLastKthNodeInDoubleList { public static class DoubleNode { public int data; public DoubleNode prev; public DoubleNode next; public DoubleNode(int data) { this.data = data; } } public static DoubleNode removeLastKthNode(DoubleNode head, int k) { if (head == null || k < 1) { return head; } DoubleNode cur = head; while (cur != null) { k--; cur = cur.next; } if (k > 0) { } else if (k == 0) { head = head.next; head.prev = null; } else { cur = head; while (++k != 0) { cur = cur.next; } DoubleNode node = cur.next.next; cur.next = node; if (node != null) { node.prev = cur; } } return head; } public static void main(String[] args) { DoubleNode node1 = new DoubleNode(1); DoubleNode node2 = new DoubleNode(2); DoubleNode node3 = new DoubleNode(3); DoubleNode node4 = new DoubleNode(4); DoubleNode node5 = new DoubleNode(5); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; removeLastKthNode(node1, 4); DoubleNode n = node1; while (n != null) { System.out.printf("%d ", n.data); n = n.next; } } } // ------ Output ------ /* 1 3 4 5 */