在单链表和双链表中删除倒数第k个节点

本文主要是介绍在单链表和双链表中删除倒数第k个节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实现的完整代码如下:

//在单链表和双链表中删除倒数第k个节点public class DeleteList{//单链表节点的定义public static class Node{int value;Node next;public Node(int data){this.value=data;}}//删除单链表中倒数第k个节点public static int DeletList_K(Node head,int k){   Node t=head; //用t指向链表的头结点if(head==null||k<1){return -10000;  //表示没有删除的数据}int leng=0; //计算链表的长度while(t!=null){t=t.next;++leng;}//System.out.println(leng); 打印出链表的长度为3if(k>leng){return -10000;  //表示没有删除的数据}for(int i=0;i<leng-k-1;i++){head=head.next;  //找到倒数第k-1个节点}Node p=head.next;  //找到倒数第k个节点  head.next=head.next.next; //删除倒数第k个节点return p.value;}//双链表节点的定义public static class Node2{int value;Node2 next,pre;public Node2(int data){this.value=data;}}//删除双链表中倒数第k个节点public static int DelteTwoList_K(Node2 head2,int k){Node2 t=head2; //用t指向链表的头结点if(head2==null||k<1){return -10000;}int leng=0; //计算双链表的长度while(t!=null){t=t.next;++leng;}//System.out.println(leng); //打印出链表的长度为3if(k>leng){return -10000;  //表示没有删除的数据}for(int i=0;i<leng-k;i++){head2=head2.next;}Node2 p=head2; //倒数第k个节点p.pre.next=p.next;  //删除倒数第k个节点return p.value;}public static void main(String []args){//删除单链表倒数第k个节点测试  链表为 1->2->3Node node=new Node(1);node.next=new Node(2);node.next.next=new Node(3);//node.next.next.next=new Node(4);System.out.println(DeletList_K(node,2));//删除双链表倒数第k个节点测试  链表为 1->2->3Node2 node2=new Node2(1);node2.next=new Node2(2);node2.next.next=new Node2(3);node2.next.pre=node2;node2.next.next.pre=node2.next;//node.next.next.next=new Node(4);System.out.println(DelteTwoList_K(node2,2));}
}

左神的代码:

public class Problem_02_RemoveLastKthNode {public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}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;}public static 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 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.print("Linked List: ");while (head != null) {System.out.print(head.value + " ");head = head.next;}System.out.println();}public static void printDoubleLinkedList(DoubleNode head) {System.out.print("Double Linked List: ");DoubleNode end = null;while (head != null) {System.out.print(head.value + " ");end = head;head = head.next;}System.out.print("| ");while (end != null) {System.out.print(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);}}