剑指offer系列12---链表倒数第k个结点

【题目】输入一个链表，输出该链表中倒数第k个结点。

【思路】方法3：设置两个指针，第一个指针先走k-1步，第2个指针开始走，(这时候第一个指针指向第k个)当第一个指针走到尾部时(即走了k步)，第一个指针即指向第k个结点。(推荐的方法)

            方法2：先获取结点个数，再顺数第n-k+1个结点 1 2 3 4 5 6

           方法1：先获取长度，再复制至数组一中，再反序加至数组2中，这时候要输出倒数第K个数即为数组2中的顺数第k-1个数。此处出现的异常不知道该怎么处理。(我的方法)

package com.exe3.offer;

/**
 * 【题目】输入一个链表，输出该链表中倒数第k个结点。
 * @author WGS
 *
 */
public class PrinkLinkNode {
    static class LinkNode{
        int val;
        LinkNode next=null;
        public LinkNode(int n){
            this.val=n;
        }
    }
    //方法3：设置两个指针，第一个指针先走k-1步，第2个指针开始走，(这时候第一个指针指向第k个)当第一个指针走到尾部时(即走了k步)，第一个指针即指向第k个结点。
    public LinkNode  printLinkNodeFromTail3(LinkNode node,int k){
        //异常处理，若头指针node为空或者输入的k结点是0
        if(node==null||k<=0){
            
            System.out.println("invalid");
            return null;
        }
        LinkNode firstIndex=node;//此处要注意，亮点
        LinkNode secondIndex=null;
        for(int i=0;i<k-1;i++){
            if(firstIndex!=null){
                firstIndex=firstIndex.next;
            }else{
                return null;
            }
        }
        //此时第一个指针已经走至第k步
        secondIndex=node;
        while(firstIndex.next!=null){
            firstIndex=firstIndex.next;
            secondIndex=secondIndex.next;
        }
        
        return secondIndex;
        
    }
    //方法2：先获取结点个数，再顺数第n-k+1个结点 1 2 3 4 5 6
    public LinkNode  printLinkNodeFromTail2(LinkNode node,int k){
        LinkNode temp=node;
        int lenOfNode=0;
        if(node==null||k<=0){
            
            System.out.println("invalid");
            return null;
        }
        //1 获取长度
        while(node!=null){
            lenOfNode++;//结点个数
            node=node.next;
        }
        int i=1;
        //2 顺数直至第n-k+1个点
        while(k<=lenOfNode &&(i!=lenOfNode-k+1)){
            i++;
            temp=temp.next;
        }
        //合理
        if(k<=lenOfNode){
            return temp;
        }
        return null;
        
    }        
    //方法1：先获取长度，再复制至数组一中，再反序加至数组2中，这时候要输出倒数第K个数即为数组2中的顺数第k-1个数。此处出现的异常不知道该怎么处理。
    public int  printLinkNodeFromTail(LinkNode node,int k){        
        LinkNode temp=node;
        int len=0;
        int m=0;
        //1 获取长度
        while(node!=null){
            len++;
            node=node.next;
        }
        if(temp==null||k<0||k>=len){
            try {
                System.out.println("invalid");
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        int[] arr1=new int[len];
        while(temp!=null){
            arr1[m++]=temp.val;
            temp=temp.next;
        }
        int[] arr2=new int[len];
        for(int i=0;i<arr1.length;i++){
            arr2[len-1-i]=arr1[i];
        }
        if(k<=len){
            return arr2[k-1];
        }
        return 0;
        
        
    }
    public static void main(String[] args){
        PrinkLinkNode p=new PrinkLinkNode();
        LinkNode node1=new LinkNode(1);
        LinkNode node2=new LinkNode(2);
        LinkNode node3=new LinkNode(3);
        LinkNode node4=new LinkNode(4);
        LinkNode node5=new LinkNode(5);
        LinkNode node6=new LinkNode(6);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        //3
        /*int n=p.printLinkNodeFromTail(node1,8);
        System.out.println(n);*/
        //2
        /*LinkNode node=p.printLinkNodeFromTail2(node1,0);
            if(node!=null){
            System.out.println(node.val);
        }else{
            System.out.println("null");
        }*/
        //3
        LinkNode node=p.printLinkNodeFromTail3(node1,0);
        if(node!=null){
            System.out.println(node.val);
        }else{
            System.out.println("null");
        }
        
    }
    
    
    
    
    
    
    
}