[数据结构与算法]剑指offer之链表中倒数最后k个结点

前言

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

示例1
输入：
{1,2,3,4,5},3
返回值：
{3,4,5}
示例2
输入：
{2},8
返回值：
{}
复制

辅助栈

核心思想: 利用栈先进后出的特性，假设将5个节点依次插入栈中，即1->2->3->4->5，则最后是将最后的节点依次输出，即输出5->4->3->2->1 ，此时，我们只要遍历栈中元素，控制计数k即得到倒数第k个元素

码上有戏

public ListNode FindKthToTail (ListNode pHead, int k) {
       if(pHead == null || k <= 0){
           return null;
       }
        
      ListNode preNode = pHead;
        for(int i = 0 ;i < k;i++){
              if(preNode == null){
                return null;
            }
            preNode = preNode.next;          
        }
        
       ListNode behind = pHead;
       while(preNode != null){
           preNode = preNode.next;
           behind = behind.next;
       }
       
       return behind;
     
    }

双指针

核心思想: 使用两个指针，前一个指针遍历到k位置停止，然后与后一个指正同时遍历，直至前一个指针到尾结点。而两个指针始终相差k个节点，最后第二个指针从逆序来看正好是倒数第k个节点

码上有戏

public ListNode FindKthToTail (ListNode pHead, int k) {
       if(pHead == null || k <= 0){
           return null;
       }
        
      ListNode preNode = pHead;
        for(int i = 0 ;i < k;i++){
              if(preNode == null){
                return null;
            }
            preNode = preNode.next;          
        }
        
       ListNode behind = pHead;
       while(preNode != null){
           preNode = preNode.next;
           behind = behind.next;
       }
     return behind;
    }