题解 | #链表中倒数最后k个结点#

题目

输入一个长度为的链表，设链表中的元素的值为a_i，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。如果该链表长度小于k，请返回一个长度为 0 的链表。

思路

首先遍历这个链表pHead，将当前结点的val值存进ArrayList集合中，然后将下一个结点赋值为pHead，直至链表为空，将所有结点的值都存进了ArrayList集合。接着判断k值，若k>list.size()或者k<=0，都返回null；若不满足这个条件则遍历这个list集合，将倒数第k个及以后的数取出来并创建结点，将集合的下一个值创结点并赋为上一个结点的next。同时新建了一个存放ListNode的队列，将每个结点都存进队列中，最后返回倒数第k个的结点，也就是最先开始入队的那一个结点。

这个思路虽然实现了，但是内存以及运行时间太大了，并不好。

第二种解法是看了别人用队列后自己思考出来的。

代码

import java.util.*;

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

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        Deque<ListNode> d = new ArrayDeque<>();
        ArrayList list = new ArrayList();
        ListNode listNode = null;
        if(pHead == null){
            return listNode;
        }else{
            while(pHead != null){
                list.add(pHead.val);
                pHead = pHead.next;
            }

            if(k>list.size() || k<=0){
                return listNode;
            }else{
                int index = (int)list.get(list.size()-k);
                ListNode node1 = new ListNode(index);
                d.addLast(node1);
                for(int i=list.size()-k+1;i<list.size();i++){
                    node1.next = new ListNode((Integer)list.get(i));
                    d.addLast(node1.next);
                    node1 = node1.next;
                }
                return d.pollFirst();
            }
        }

    }
}

import java.util.*;
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        //定义一个ListNode类型的队列
        Deque<ListNode> d = new ArrayDeque<>();
        ListNode listNode = null;
        if(pHead == null){
            return listNode;
        }else{
            while(pHead != null){
                d.addLast(pHead);
                pHead = pHead.next;
            }

            if(k>d.size() || k<=0){
                return listNode;
            }else{
                //关键代码：因为要返回倒数第k个的结点，故将队列中后进来的
                //那k个结点出队，最后k次出队的就是要返回那一个结点
                for(int i=1;i<=k;i++){
                    listNode = d.pollLast();
                }
                return listNode;
            }
        }

    }
}