剑指offer---链表相关

1 输入一个链表，输出该链表中倒数第k个结点

public class ListNode {  
    int val;  
    ListNode next = null;  
  
    ListNode(int val) {  
        this.val = val;  
    }  
}  


    public ListNode FindKthToTail(ListNode head,int k){
        ListNode front = head;
        int i =0;
        for (;front !=null && i<k;i++){
            front = front.next;
        }
        //如果k大于链表的长度或者k小于0，返回null
        if(i !=k){
            return null;
        }
        ListNode behind = head;
        while (front !=null){
            front = front.next;
            behind = behind.next;
        }
        //如果k等于0,则behind为null
        return behind;

    }

分析，因为倒数第k个结点不知道是第几个结点，我们又不能采用倒序的方法依次获取每个元素。我们可以用错位超越的方法。即当到达最后一个的时候，我们知道。所有，先让一个走K步，然后第二个和第一个在同时往前取，等第一个到达终点的时候，第二个刚好还有k个，即倒数第k个元素

2 反转一个链表

//输入一个链表，反转链表后，输出链表的所有元素

public ListNode reverseMode(ListNode head){
        if(head == null){
            return null;
        }
        //head为当前节点,如果当前节点为空的话,那么什么也不做,直接返回null
        ListNode pre = null;
        ListNode next ;
        //当前节点是head,pre为当前节点的前一节点,next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从
        // pre->head->next1->next2变成
        // pre<-head next1 ->next2
        //即pre让节点可以反转所指方向,但反转之后如果不用next节点保存next1节点的话
        //此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1 -> 2 -> 3 -> 4 ->5
        //1 <- 2 <- 3 <- 4 <-5
        while (head !=null){
           //做循环,如果当前节点不为空的话,始终执行此循环,此循环的目的就是让当前节点
            //从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息,保证单链表不会因此失去head
            //节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了,代码如下
            head.next = pre;
            //head指向pre后,就继续依次反转下一个节点
            //让pre，head,next依次向后移动一个节点,继续下一次的指针反转
            pre = head;
            head = next;
        }

        //如果head为null的时候,pre就为最后一个节点了,但是链表已经反转完毕
        //pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到反转后的链表
        return pre;
    }