题目：分别实现两个函数，一个可以删除单链表中倒数第K个节点，另一个可以删除双链表中倒数第K个节点。
单链表：
思路：
1——>2——>3——>4——>5 k=3 删除节点3
每往后遍历一个，k就减 1。
当遍历完之后，k的三种情况：
（1）k如果大于0，直接返回原来头节点
（2）k如果为0，那么要删除的节点就是头节点。
（3）如果k<0，则要删除的节点是中间节点或尾节点，这时候需要重新遍历一次，每走一步k就加1，当k=0时停止，当前节点就是要删除节点的前一个节点。
比如链表为 1—2—3—4—5 五个节点，删除倒数第3个，当第一次遍历完之后，k不断减减为-2，这时链表从头再次遍历，然后k再加加，加到0的时候，当前遍历到2节点。是要删除节点的前一个节点。
代码实现：
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;
}
//当k为0的时候，正好删掉的是头节点，比如总共三个节点，删除倒数第3个，就删除的是头节点。
if (k == 0) {
head = head.next;
}
//当k为负值的时候，说明要删除的节点是链表中间的节点。比如总共五个节点，删除倒数第三个，当链表走完之后，k为-2
if (k < 0) {
cur = head;
while (++k != 0) {
cur = cur.next;
}
cur.next = cur.next.next;//删除当前节点的下一个节点
}
return head;
}双链表：
双链表的思路和单链表一样，只要删除节点的时候注意连上last就行。
public class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
this.value = 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) {
head = head.next;
head.last = null; //头节点的前一个是null
}
if (k < 0) {
cur = head;
while (++k != 0) {
cur = cur.next;
}
DoubleNode newNode = cur.next.next;//当删除的节点是倒数第一个的时候 此处newNode是null 直接cur.next=null就行
cur.next = newNode;
if (newNode != null) {
newNode.last = cur;
}
}
return head;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/87975.html
