剑指Offer面试题：17.链表中倒数第k个结点

一、题目
————————————————
题目描述
输入一个链表，输出该链表中倒数第k个结点。
————————————————
二、思路
————————————————
方法一：
设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。

————————————————
方法二：利用栈，先进后出
————————————————
三、解决问题
————————————————
测试算例　

　　1.功能测试（第k个结点分别在链表的中间，头结点和尾结点）

　　2.特殊测试（头结点为null，k超出范围）
————————————————

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020\3\11 0011 10:15
 */
//输入一个链表的头结点，从尾到头反过来打印出每个结点的值。结点定义如下：
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020-03-20 20:15
 */

import java.util.Stack;

/**
 * 题目：
 * 输入一个链表，输出该链表中倒数第k个结点。
 * 为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。
 * 例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。
 * 这个链表的倒数第3个结点是值为4的结点。
 */

public class Solution17 {
    public static void main(String[] args) {
        Solution17 demo = new Solution17();
        System.out.println("==============================");
        System.out.println("test1");
        demo.test1();
        System.out.println("==============================");
        System.out.println("test2");
        demo.test2();
        System.out.println("==============================");
        System.out.println("test3");
        demo.test3();
        System.out.println("==============================");
        System.out.println("test4");
        demo.test4();
        System.out.println("==============================");
        System.out.println("test5");
        demo.test5();
        System.out.println("==============================");
        System.out.println("test6");
        demo.test6();
        System.out.println("==============================");
    }
    //方法1：利用两个相距为k-1的指针
    public ListNode FindKthToTail1(ListNode head,int k) {
        //不满足的条件
        if(null == head || k <= 0){
            return null;
        }
        ListNode pAhead = head;
        //1.先让 pAhead 移动 K 个节点，则还有 N - K 个节点可以移动
        while (pAhead != null && k-- > 0){
            pAhead = pAhead.next;
        }
        //给定k的长度大于链表实际长度
        if (k > 0){
            return null;
        }
        //2.此时让 pAhead 和 pBehind 同时移动
        //可以知道当 pAhead 移动到链表结尾时，pBehind 移动到第 N - K 个节点处
        //该位置就是倒数第 K 个节点
        ListNode pBehind = head;
        while (pAhead != null) {
            pAhead = pAhead.next;
            pBehind = pBehind.next;
        }
        return pBehind;

    }
    //方法2：利用栈-先进后出
    public ListNode FindKthToTail2(ListNode head,int k) {
        if(null == head || k <= 0){
            return null;
        }
        int numbOfList = 1;
        Stack<ListNode> st = new Stack<ListNode>();
        st.push(head);
        ListNode node = head.next;
        while(node != null){
            numbOfList++;
            st.push(node);
            node = node.next;
        }
        if(k > numbOfList){
            return null;
        }else{
            for (int i = 1; i <= k; i++) {
                node = st.pop();
            }
            return node;
        }
    }
    //=====================测试代码=======================
    /*
     * null
     */
    void test1() {
        ListNode head1=null;
        ListNode result1=FindKthToTail1(head1, 1);
        if(result1 == null)
            System.out.println("test1 passed!");
        else
            System.out.println("test1 failed!");
        System.out.println("===========方法二：利用栈-先进后出============");
        ListNode head2=null;
        ListNode result2=FindKthToTail2(head2, 1);
        if(result2 == null)
            System.out.println("test1 passed!");
        else
            System.out.println("test1 failed!");
    }

    /*
     * k超出范围
     */
    void test2() {
        ListNode head=new ListNode(2);
        ListNode result=FindKthToTail1(head, 2);
        if(result == null)
            System.out.println("test2 passed!");
        else
            System.out.println("test2 failed!");
        System.out.println("===========方法二：利用栈-先进后出============");
        ListNode head2=new ListNode(2);
        ListNode result2=FindKthToTail2(head2, 2);
        if(result2 == null)
            System.out.println("test2 passed!");
        else
            System.out.println("test2 failed!");
    }

    /*
     * 单个结点
     */
    void test3() {
        ListNode head=new ListNode(1);
        ListNode result=FindKthToTail1(head, 1);
        if(result.val==1)
            System.out.println("test3 passed!");
        else
            System.out.println("test3 failed!");
        System.out.println("===========方法二：利用栈-先进后出============");
        ListNode head2=new ListNode(1);
        ListNode result2=FindKthToTail2(head2, 1);
        if(result2.val == 1)
            System.out.println("test3 passed!");
        else
            System.out.println("test3 failed!");

    }
    /*
     * 尾结点
     */
    void test4() {
        ListNode node1=new ListNode(1);
        ListNode node2=new ListNode(2);
        ListNode node3=new ListNode(3);
        ListNode node4=new ListNode(4);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        ListNode result=FindKthToTail1(node1, 1);
        if(result.val==4)
            System.out.println("test4 passed!");
        else
            System.out.println("test4 failed!");
        System.out.println("===========方法二：利用栈-先进后出============");
        ListNode result2=FindKthToTail2(node1, 1);
        if(result2.val==4)
            System.out.println("test4 passed!");
        else
            System.out.println("test4 failed!");
    }
    /*
     * 中间结点
     */
    void test5() {
        ListNode node1=new ListNode(1);
        ListNode node2=new ListNode(2);
        ListNode node3=new ListNode(3);
        ListNode node4=new ListNode(4);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        ListNode result=FindKthToTail1(node1, 2);
        if(result.val==3)
            System.out.println("test5 passed!");
        else
            System.out.println("test5 failed!");

        System.out.println("===========方法二：利用栈-先进后出============");
        ListNode result2=FindKthToTail2(node1, 2);
        if(result2.val==3)
            System.out.println("test5 passed!");
        else
            System.out.println("test5 failed!");

    }
    /*
     * 头结点
     */
    void test6() {
        ListNode node1=new ListNode(1);
        ListNode node2=new ListNode(2);
        ListNode node3=new ListNode(3);
        ListNode node4=new ListNode(4);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        ListNode result=FindKthToTail1(node1, 4);
        if(result.val==1)
            System.out.println("test6 passed!");
        else
            System.out.println("test6 failed!");
        System.out.println("===========方法二：利用栈-先进后出============");

        ListNode result2=FindKthToTail2(node1, 4);
        if(result2.val==1)
            System.out.println("test6 passed!");
        else
            System.out.println("test6 failed!");
    }
}

输出

==============================
test1
test1 passed!
===========方法二：利用栈-先进后出============
test1 passed!
==============================
test2
test2 passed!
===========方法二：利用栈-先进后出============
test2 passed!
==============================
test3
test3 passed!
===========方法二：利用栈-先进后出============
test3 passed!
==============================
test4
test4 passed!
===========方法二：利用栈-先进后出============
test4 passed!
==============================
test5
test5 passed!
===========方法二：利用栈-先进后出============
test5 passed!
==============================
test6
test6 passed!
===========方法二：利用栈-先进后出============
test6 passed!
==============================

Process finished with exit code 0

————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。