首页 > 试题广场 >

链表中倒数第k个结点

[编程题]链表中倒数第k个结点
  • 热度指数：1294367 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入一个链表，输出该链表中倒数第k个结点。
示例1

输入

1,{1,2,3,4,5}

输出

{5}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
推荐
Python
人民的名义头像 人民的名义
Python 设置两个指针，p1，p2，先让p2走k-1步，然后再一起走，直到p2为最后一个 时，p1即为倒数第k个节点 
class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head==None or k<=0:
            return None
        #设置两个指针，p2指针先走（k-1）步，然后再一起走，当p2为最后一个时，p1就为倒数第k个 数
        p2=head
        p1=head
        #p2先走，走k-1步，如果k大于链表长度则返回 空，否则的话继续走
        while k>1:
            if p2.next!=None:
                p2=p2.next
                k-=1
            else:
                return None
#两个指针一起 走，一直到p2为最后一个,p1即为所求
        while p2.next!=None:
            p1=p1.next
            p2=p2.next
        return p1


编辑于 2019-08-13 14:41:34 回复(23)
C/C++
冰殇灬头像 冰殇灬

设置两个指针 fast 、slow，fast先走k步，如果走不到第k步（nullptr节点是可以走到的，但是nullptr节点没有next，所以只能走到nullptr），说明链表长度不够k，直接返回nullptr；然后，令 fast 和 slow 开始同步往下移动，直到 fast 移动到nullptr，此时slow就是倒数第 k 个节点的，返回即可。
code:

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead == nullptr || k < 1){
            return nullptr;
        }
        ListNode *pre = pListHead;
        ListNode *last = pListHead;
        while(k > 0){
            if(last == nullptr){
                return nullptr;
            }
            last = last->next;
            k--;
        }
        while(last != nullptr){
            last = last->next;
            pre = pre->next;
        }
        return pre;
    }
};
发表于 2017-12-04 09:45:44 回复(6)
黎离头像 黎离 
//递归简洁明了
unsigned int cnt=0;
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    if(pListHead==NULL)
        return NULL;
    ListNode* node=FindKthToTail(pListHead->next,k);
    if(node!=NULL)
        return node;
    cnt++;
    if(cnt==k)
        return pListHead;
    else
        return NULL;
}

发表于 2017-10-06 15:48:00 回复(9)
努力编程头像 努力编程 
public ListNode FindKthToTail(ListNode head,int k) {
    	ListNode p = head;
    	while(k-- != 0){
    		if(p == null)
    			return null;
    		p = p.next;
    	}
    	while(p != null){
    		p = p.next;
    		head = head.next;
    	}
    	return head;
    }

发表于 2016-08-25 18:07:47 回复(8)
和时间赛跑头像 和时间赛跑 
 if(head==null||k<=0)return null;
		 	ListNode nodePre=head;
		 	ListNode nodeLast=head;
		 	
		 	for(int i=1;i<k;i++){
		 		if(nodePre.next!=null)nodePre=nodePre.next;
		 		else return null;
		 	}
		 	
		 	while(nodePre.next!=null){
		 		nodePre = nodePre.next;
		 		nodeLast=nodeLast.next;
		 	}
		 	return nodeLast;

发表于 2015-08-07 22:26:36 回复(16)
菩提旭光头像 菩提旭光 
  最佳代码：Java代码，通过
编辑于 2019-08-13 14:41:34 回复(90)
晓宇大美女~头像 晓宇大美女~ 
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null)
			return null;
		int count = 0;
		ListNode temp = head;
		for (int i = 0; temp != null; temp = temp.next) {
			count++;
		}
		if(k>count)
			return null;
		System.out.println(count);
		//一共有count个，倒数第k个就是正数第count-k+1,下标是count-k
		for(int i = 0;i<count-k;i++){
			head = head.next;
		}
		return head;
    }
}

发表于 2016-06-28 17:20:58 回复(11)
CrazyZfp头像 CrazyZfp 
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
		if(k<1)
            return null;
        Q<ListNode> q = new Q<ListNode>(k);
        while(head!=null){
            q.add(head);
            head = head.next;
        }
        return q.get();
    }
}

class Q<T>{
	private Object[] arr;
	private int index = 0;
	
	public Q(int l){
		arr = new Object[l];
	}
	
	public void add(T t){
        arr[index++] = t;
		if(index == arr.length)
			index = 0;
	}
	public T get(){
		return (T)arr[index];
	}
}
自己封装了一个循环数组来解决...

发表于 2015-11-24 20:22:40 回复(0)
Java
yellow要经历的世界头像 yellow要经历的世界

看了其他的JAVA答案，感觉不是很好，都用了复杂的数据结构

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k==0) return null; //判断k为0，返回null的情况
        ListNode t = head; //处理长度的第一个指针
        int N = 0; //链表长度
        ListNode ln= null; //记录距离结尾K长度的node
        while(t!=null){
            N ++;
            if(N == k) ln = head;//当长度超过k的时候，才有值
            else if(N>k) ln = ln.next; //当N长度大于k的时候，每一次for循环前移
            t = t.next; //处理长度的指针前移
        }

        return ln; //for循环结束，得到的距离k的Node，可以为空
    }
}
发表于 2017-09-19 12:04:37 回复(3)
牛客749711号头像 牛客749711号 
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
  {
    if(pListHead==NULL||k<=0)//如果输入空链表或k<=0
        return NULL;
    stack<ListNode*> stk;
    ListNode* p=pListHead;
    while(p!=NULL){
        stk.push(p);
        p=p->next;
    }
    if(stk.size()>=k){ //如果k的值大于链表中的元素数目
        while((--k)>0){
            stk.pop();
        }
        return stk.top();
    }else
        return NULL;
    }
}

编辑于 2016-04-30 21:53:39 回复(2)
imwtr头像 imwtr 
function FindKthToTail(head, k)
{
    let val = [];
    
    while (head) {
        // 之前有一道题是返回值，这道题是返回这个链表对象。。。。
        val.unshift(head);
        head = head.next;
    }
    
    return val[k - 1];
}

发表于 2018-08-26 19:45:13 回复(0)
击水3千头像 击水3千 
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    	if(!pListHead||k==0)return NULL;
        ListNode* p=pListHead;
        k--;
        while(k--){
           if(p->next==NULL)return NULL;
            p=p->next;
        }
        while(p->next!=NULL){
            p=p->next;
            pListHead=pListHead->next;
        }
       return pListHead;
      }
};

发表于 2017-02-25 14:38:50 回复(0)
Echo001头像 Echo001 
//使用Vector做中间存储
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    	if(pListHead == NULL || k <= 0)
            return NULL;
         vector<ListNode *> vec;
        ListNode *pNode = pListHead;
        while(pNode != NULL){
            vec.push_back(pNode);
            pNode = pNode->next;
        }
        if(vec.size() < k){
            return NULL;
        }       
        
        return vec[vec.size()-k];
    }
};

发表于 2016-09-18 13:41:36 回复(1)
Java
宸风头像 宸风 
//用栈的先进后出特性来做，测试通过
import java.util.Stack;
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        Stack<ListNode> stack=new Stack<ListNode>();
        ListNode list=null;
        ListNode tmp=head;
        int n=0;
        while(tmp!=null){     //先判断链表是否具有k个节点
            tmp=tmp.next;
            n++;
        }
        if(n<k){            //少于k个节点返回null
           return list;
        }
        
        while(head!=null){    //大于等于k个节点，则全压入栈，再出栈k次
           stack.push(head);
           head=head.next;
        }
        for(int j=k;j>0;j--){
         list=stack.pop();
        }
         return list;
    }
}


发表于 2016-07-09 23:54:14 回复(3)
Aurora1头像 Aurora1 
    public ListNode FindKthToTail(ListNode head, int k) {
        ListNode p, q;
        for (p = q = head; p != null; p = p.next, k--)
            if (k <= 0)
                q = q.next;
        return k <= 0 ? q : null;
    }

编辑于 2020-09-02 23:23:29 回复(87)
Java
张诗烨头像 张诗烨

使用ArrayList容器来解决，逻辑上比较简单。 

import java.util.ArrayList;
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ArrayList list = new ArrayList();
        while(head!=null){
            list.add(head);
            head = head.next;
        }
        if(list.size()<k || k <=0)
            return null;
        else
            return (ListNode)list.get(list.size()-k);
    }
}
编辑于 2019-07-25 09:36:32 回复(0)
Python
[图片]头像 [图片] 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        front = head
        later = head
        for i in range(k):
            if front==None:
                return
            if front.next == None and i==k-1:
                return head
            front = front.next
        while front.next != None:
            front = front.next
            later = later.next
        return later.next

发表于 2016-08-07 16:30:32 回复(3)
Java
来个大厂offer吧头像 来个大厂offer吧 
//方法1:
    //倒数第k个就是正数第size - k + 1个
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k <= 0){
            return null;
        }
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            cur = cur.next;
            count++;
        }
        if(k > count){
            return null;
        }
        count = count - k + 1;
        while(count > 1){
            head = head.next;
            count--;
        }
        return head;
    }

    //方法2:
    //借鉴评论中的评论：
    //相当于制造了一个K长度的尺子，把尺子从头往后移动，
    //当尺子的右端与链表的末尾对齐的时候，尺子左端所在的结点就是倒数第k个结点
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k <= 0){
            return null;
        }
        ListNode cur1 = head;
        ListNode cur2 = head;

        //cur2先走k-1步，来到正数第k个位置
        while(k > 1){
            if(cur2.next != null){
                cur2 = cur2.next;
                k--;
            }else {
                return null;
            }

        }
        //此时就构成了一个以cur1和cur2为端点的尺子
        //当cur2与最后一个重合时，cur1就是倒数第k个
        while(cur2.next != null){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
发表于 2019-08-18 20:21:57 回复(0)
西瓜爱offer头像 西瓜爱offer 
//遍历二次
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
    if (pListHead == NULL)
        return NULL;
    //求链表的长度
    int len = 0;
    ListNode *p = pListHead;
    while (p)
    {
        p = p->next;
        len++;
    }
    if (k > len)
        return NULL;
    int n = len - k;
    while (n-- > 0) {
        pListHead = pListHead->next;
    }
    return pListHead;
}

//遍历一次
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
    if (pListHead == NULL)
        return NULL;

    ListNode *p = pListHead, *q = pListHead;
    int i = 1;//链表的第一个节点
    for (; p != NULL; i++)
    {
        p = p->next;
        //当前面节点行动k步后，后面节点也开始移动，前面节点比后面节点多运动了k步，当前面节点到达尾节点，后面节点刚好在倒数k个节点
        if (i > k)
            q = q->next;
    }
    return i < k ? NULL : q;
}

发表于 2019-07-23 16:04:59 回复(0)
打工不可能打工的头像 打工不可能打工的 

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

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.Stack;

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if (head == null || k == 0) {
            return null;
        }
        Stack<ListNode> arrList = new Stack<ListNode>();
        ListNode cur = head;
        int size = 0;
        while (cur != null) {
            arrList.push(cur);
            size++;
            cur = cur.next;
        }
        // ListNode res = null;
        if (k > size) {
            return null;
        }
        while (--k != 0) {
            arrList.pop();
        }
        return arrList.pop();
    }
}

发表于 2018-07-13 23:43:50 回复(0)
Java
Real_Mardird_8头像 Real_Mardird_8 
import java.util.Stack;
public class Solution {
    //通过一个辅助栈，利用栈的后进先出特点
    //所有结点进栈，再出栈k个
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null){
            return null;
        }
        if(k<0){
            return null;
        }
        Stack <ListNode> stack=new Stack<ListNode> ();
        ListNode nodek=null;    //记录第k个结点
        ListNode current =head;
        int size=0;//记录结点的个数
        while(current!=null){
            stack.push(current);
            current=current.next;
            size++;
        }
        if(k>size){
            return null;
        }
        for(int i=0;i<k;i++){
           nodek= stack.pop();
        }
        return nodek;
    }
}

发表于 2018-02-23 11:16:51 回复(0)
提交观点

问题信息

链表 双指针
难度：
1898条回答 206078浏览

热门推荐

通过挑战的用户

相关试题

链表中倒数第k个结点

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号