题目：
分别实现两个函数，一个可以删除单链表中倒数第K个节点，另一个可以删除双链表中倒数第K个节点。
要求：
如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。
解答：
让链表从头走到尾，每移动一步，就让K值减一，
示例：
第一种情况：
链表走到结尾时，如果K值大于0，说明不用调整链表，因为链表根本没有倒数第K个节点，此时将原链表直接返回即可；
第二种情况：
链表走到结尾时，如果K值等于0，说明链表倒数第K个节点就是头结点，此时直接返回head.next，相当于删除了头结点。
第三种情况：（当链表走到结尾时，当K的值小于零时，）
K< 0 时的处理方法：
链表长度为N,要删除倒数第K个节点，那么倒数第K个节点的前一个结点就是第N-K个节点。在第一次遍历之后，K的值变为了K-N。第二次遍历时，K的值不断加1.加到0就停止遍历，所在的位置就是第N-K个节点的位置。
public class Problem02_RemoveLastKthNode {
// 单链表
public static class Node {
public int value;
public Node next;
public Node (int data){
this.value = data;
}
}
// 双链表
public static class DoubleNode{
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode (int data) {
this.value = data;
}
}
// 删除单链表中倒数第K个结点
/* 1. 异常情况考虑：---- 链表为空，K值<1, 返回头结点
* 2. 其他（链表非空，K值>0） 策略：从头结点开始往后k--
* 2.1. 到达链表尾部时(cur = null)， k>0, 则不存在K结点；
* 2.2. 到达链表尾部时(cur = null)， k=0, 则头结点head就是K结点；
* 2.3. 到达链表尾部时(cur = null)， k<0, 则需要找到删除K结点的前一个结点；
* 详情：
* 重新从头结点开始，每移动一步，就让K值加1；
* 当k=0时，移动停止，移动到的结点就是要删除的结点的前一个结点
*/
public static Node removeLastKthNode(Node head, int lastKth){
if (head == null || lastKth < 1){
return head;
}
Node cur = head;
while(cur != null) {
lastKth--;
cur = cur.next;
}
if (lastKth == 0){
head = head.next;
}
if (lastKth < 0){
cur = head;
while( ++lastKth != 0){
cur = cur.next;
}
cur.next = cur.next.next;
}
return head;
}
// 删除双链表中倒数第K个结点(同单链表，注意last指针的重连即可)
public static DoubleNode removeLastKthNode(DoubleNode head, int lastKth){
if (head == null || lastKth < 1){
return head;
}
DoubleNode cur = head;
while(cur != null){
lastKth--;
cur = cur.next;
}
if(lastKth == 0){
head = head.next;
head.last = null;
}
if (lastKth < 0){
cur = head;
while(++lastKth != 0){
cur = cur.next;
}
DoubleNode newNext = cur.next.next;
cur.next = newNext;
if (newNext != null) {
newNext.last = cur;
}
}
return head;
}
// 打印链表值函数
public static void printLinkedList(Node head) {
System.out.println("Linked list: ");
while(head != null){
System.out.println(head.value + " ");
head = head.next;
}
System.out.println();
}
public static void printDoubleLinkedList(DoubleNode head){
System.out.println("DoubleLinked list: ");
DoubleNode end = null;
while (head != null) {
System.out.println(head.value + " ");
end = head;
head= head.next;
}
System.out.println("**********");
while(end != null) {
System.out.println(end.value + " ");
end = end.last;
}
System.out.println();
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.next = new Node(2);
head1.next.next = new Node(3);
head1.next.next.next = new Node(4);
head1.next.next.next.next = new Node(5);
head1.next.next.next.next.next = new Node(6);
printLinkedList(head1);
head1 = removeLastKthNode(head1, 3);
// head1 = removeLastKthNode(head1, 6);
// head1 = removeLastKthNode(head1, 7);
printLinkedList(head1);
DoubleNode head2 = new DoubleNode(1);
head2.next = new DoubleNode(2);
head2.next.last = head2;
head2.next.next = new DoubleNode(3);
head2.next.next.last = head2.next;
head2.next.next.next = new DoubleNode(4);
head2.next.next.next.last = head2.next.next;
head2.next.next.next.next = new DoubleNode(5);
head2.next.next.next.next.last = head2.next.next.next;
head2.next.next.next.next.next = new DoubleNode(6);
head2.next.next.next.next.next.last = head2.next.next.next.next;
printDoubleLinkedList(head2);
head2 = removeLastKthNode(head2, 3);
// head2 = removeLastKthNode(head2, 6);
// head2 = removeLastKthNode(head2, 7);
printDoubleLinkedList(head2);
}
}
结果：
Linked list:
1
2
3
4
5
6 Linked list:
1
2
3
5
6 DoubleLinked list:
1
2
3
4
5
6
**********
6
5
4
3
2
1 DoubleLinked list:
1
2
3
5
6
**********
6
5
3
2
1