JZ14 链表中倒数最后k个节点

描述

输入一个链表,输出一个链表,该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。

如果该链表长度小于k,请返回一个长度为 0 的链表。

示例1

输入:{1,2,3,4,5},1

返回值:{5}

 1.遍历两次,第一次记个数,第二次找倒数

package com.LeetCodeProblem.JZ;
import java.util.*;

public class JZ14 {
    public ListNode FindKthToTail (ListNode pHead, int k) {

        if(k<=0||pHead==null) return null;//  if(k<=0||pHead.equal(null)) return null;不行

        int count=0;

        ListNode temp=pHead;

        while (temp!=null){
            count++;
            temp=temp.next;
        }

        if(count<k) return null;

        temp=pHead;

        for (int i = 0; i < count - k; i++) {
            temp=temp.next;
        }
        return temp;
    }


    public class ListNode {
         int val;
         ListNode next = null;

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

    }
}

2.快慢指针

 思路:

使用快慢指针

先让快指针走k个,然后快慢指针一起走
当快指针为null时,慢指针就为所求

如何判断k是否合法呢?
在快指针走k个后,如果k大于链表长度
就会在循环里为null,这时候就说明k太大而不合法

而当快指针走完后,循环结束
正好为null,则此时结果正好是pHead。

    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead == null || k <= 0) return null;
        //slow为慢指针,p为快指针
        ListNode p = pHead,slow = pHead;
        for(int i = 0;i < k;i++){
            //循环里p如果为null,说明k已经超出链表长度范围
            if(p == null) return null;
            p = p.next;
        }
        //p如果正好为null,则所求为倒数第链表长度个,为pHead
        if(p == null) return pHead;
        //快慢指针同时往右移
        while(p != null){
            p = p.next;
            slow = slow.next;
        }
        return slow;
    }

上一篇:单链表详解(文末含有经过完整测试的全部代码~需要可自取)


下一篇:带头双向循环链表的实现