面试题22: 链表中倒数第k个节点

package cn.zxy.interview;

import cn.zxy.interview.utils.ListNode;
import cn.zxy.interview.utils.UtilsLinkedList;
import org.junit.Test;

/**
 * 双指针:
 * 先让第一个指针走k步(具体k/k+1/k-1用具体的例子试一下, 实验结果是k), 然后一起走, 当先走的到达null时, 后走的恰好指向倒数第k个
 */

public class A22_kFromTail {
    @Test
    public void main(){
        ListNode root = UtilsLinkedList.build();
        UtilsLinkedList.showList(root);
        kFromTail(root, 1);

        ListNode node1 = new ListNode(1, null);
        ListNode node2 = new ListNode(2, null);
        ListNode node3 = new ListNode(3, null);

        node2.next = node3;
        node1.next = node2;
        root.next = node1;


        middleNode(root);

    }

    public void kFromTail(ListNode root, int kStep){
        if(root == null || root.next == null) return;
        // 如果输入为0, 首先这是没有意义的输入, 再次此时两个指针会一起走到null 最后报空指针异常
        if(kStep <= 0) return;

        ListNode pStart = root.next;
        ListNode pEnd = root.next;

        int k = kStep;

        while(k-- > 0){
            if(pEnd == null) return; //如果没有走完k步就到了尾部 说明非法输入 返回
            pEnd = pEnd.next;
        }

        while (pEnd != null){
            pStart= pStart.next;
            pEnd = pEnd.next;
        }

        System.out.println("倒数第" + kStep + "个数是" + pStart.value);
    }

    /**
     * 扩展: 求链表中间节点
     * @param root
     */

    public void middleNode(ListNode root){
        if(root == null || root.next == null) return;

        ListNode pStart = root.next;
        ListNode pEnd  = root.next;

        while(pEnd != null){
            pEnd = pEnd.next;
            if(pEnd == null){
                break;
            }else {
                pEnd = pEnd.next;
            }
            pStart = pStart.next;
        }
        System.out.println(pStart.value);
    }
}