代码语言：javascript复制
/**
*
*/
package com.cherish.SwordRefersToOffer;
/**
* @author acer
*
*/
public class test_22链表中倒数第k个节点 {
/**
*
*/
public test_22链表中倒数第k个节点() {
// TODO 自动生成的构造函数存根
}
public static class ListNode{
private int val;
ListNode next = null;
ListNode(int val){
this.val = val;
next = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成的方法存根
ListNode head = new ListNode(1);
//给一个链表赋值
for(int i = 2;i<10;i ) {
insertNodeFromTail(head,new ListNode(i));
}
printListNode(head);
System.out.println(FindKthToTail(head,4).val);
System.out.println(listNodeLength(head));
System.out.println(deleteFromIndex(head,4));
printListNode(head);
System.out.println(listNodeLength(head));
System.out.println(FindKthToTail(head,4).val);
}
//找到倒数第k个节点
public static ListNode FindKthToTail(ListNode head,int k) {
if(head == null||k <= 0) {
return null;
}
ListNode p1 = head;
ListNode p2 = head;
for(int i = 1;i<k;i ) {
if(p1.next != null) {
p1 = p1.next;
}else {
return null;
}
}
while(p1.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
//从头部插入新节点
public static void insertNodeFromHead(ListNode head,ListNode newNode)
{
newNode.next = head;
head = newNode;
}
//从尾部插入新节点
public static void insertNodeFromTail(ListNode head,ListNode newNode)
{
if(head == null) {
head = newNode;
return;
}
ListNode temp = head;//用temp代替head去遍历找到最后一个节点，一定不要用head自己去遍历，不然就找不到链表头了
while(temp.next != null) { //下一节点不为空
temp = temp.next;
}
temp.next = newNode;//找到最后一个节点后把新节点插入进去
}
//计算链表的长度
public static int listNodeLength(ListNode head) {
if(head ==null) {
return 0;
}
ListNode temp = head;
int length = 0;
while(temp.next != null) {
length ;
temp = temp.next;
}
return length;
}
//从特定位置删除链表
public static boolean deleteFromIndex(ListNode head,int deleteIndex)
{
if(head == null || deleteIndex<1) {
return false;
}
if(deleteIndex == 1) {
head = head.next;
return true;
}
int index = 1;
ListNode temp = head;
ListNode deleteNode;
while(temp.next != null && index < deleteIndex) {
index ;
temp = temp.next;
}
deleteNode = temp.next;
temp.next = deleteNode.next;
return true;
}
//按顺序输出链表
public static void printListNode(ListNode head)
{
ListNode temp = head;
while(temp.next != null)
{
System.out.print(temp.val);
System.out.print("t");
temp = temp.next;
}
System.out.println();
}
}
