首页 > 试题广场 > 链表中倒数第k个结点
[编程题]链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
算法知识视频讲解

1324个回答

添加回答
考研成功就女装头像 考研成功就女装 
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (k < 1) { return 0; }
        if (pListHead == NULL) { return 0; }
                 ListNode* now = pListHead;
        ListNode* dk = pListHead;
        
        for (int i = 0; i < k - 1; i++) {
            now = now->next;
            if (now == NULL) { return now; }
        }
        
        while (now->next != NULL) {
            now = now->next;
            dk = dk->next;
        }
        
        return dk;
    }
};
首先，分两种情况特判一下，倒数第0位不存在，然后，链表不存在，这是不行的。
第二，判断链表长度是不是大于k-1，长度小于k-1就出NULL
最后，找倒数第k位，一个指针指向链表尾，另一个指针指向链表尾的前k-1个，因此另一个指针就指向了倒数第k位。
空间复杂度O(1)，时间复杂度O(N)，恰好只遍历链表一次
发表于 2018-04-16 20:10:37 回复(0)
更多回答
推荐
菩提旭光头像 菩提旭光
最佳代码：Java代码，通过校验。代码思路如下：两个指针，先让第一个指针和第二个指针都指向头结点，然后再让第一个指正走(k-1)步，到达第k个节点。然后两个指针同时往后移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了。。
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null||k<=0){
            return null;
        }
        ListNode pre=head;
        ListNode last=head;       
        for(int i=1;i<k;i++){
            if(pre.next!=null){
                pre=pre.next;
            }else{
                return null;
            }
        }
        while(pre.next!=null){
            pre = pre.next;
            last=last.next;
        }
        return last;
    }
}
编辑于 2015-08-25 17:44:14 回复(76)
Aurora1头像 Aurora1 
public ListNode FindKthToTail(ListNode head,int k) { //5,{1,2,3,4,5}
		ListNode p, q;
		p = q = head;
		int i = 0;
		for (; p != null; i++) {
			if (i >= k) 
				q = q.next;
			p = p.next;
		}
		return i < k ? null : q;
    }

编辑于 2016-04-04 10:53:47 回复(48)
渡不过己头像 渡不过己 
时间复杂度O(n),一次遍历即可
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode pre=null,p=null;
        //两个指针都指向头结点
        p=head;
        pre=head;
        //记录k值
        int a=k;
        //记录节点的个数
        int count=0;
        //p指针先跑，并且记录节点数，当p指针跑了k-1个节点后，pre指针开始跑，
        //当p指针跑到最后时，pre所指指针就是倒数第k个节点
        while(p!=null){
            p=p.next;
            count++;
            if(k<1){
                pre=pre.next;
            }
            k--;
        }
        //如果节点个数小于所求的倒数第k个节点，则返回空
        if(count<a) return null;
        return pre;
           
    }
}

发表于 2015-09-07 09:52:17 回复(35)
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


发表于 2017-10-18 16:47:48 回复(8)
Python
华科平凡头像 华科平凡

明明是head.val，偏偏要写成head才通过？

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        res=[]
        while head:
            res.append(head)
            head=head.next
        if k>len(res) or k<1:
            return
        return res[-k]
编辑于 2017-12-08 10:05:53 回复(12)
PandaMaomao头像 PandaMaomao
使用Stack，将结点压入栈中，再取出第k个就好 
if(head == null || k ==0 ){
			return null;
		}
		
		//可以先把链表反转，然后找出第k个
		Stack<ListNode> stack = new Stack<ListNode>();
		int count = 0;
		while(head != null){
			stack.push(head);
			head = head.next;
			count++;
		}
		
		if(count < k){
			return null;
		}
		
		ListNode knode = null;
		for(int i = 0; i < k; i++){
			knode = stack.pop();
		}
		
		
		return knode;

发表于 2017-03-12 22:55:19 回复(10)
C/C++
EricZeng头像 EricZeng 
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    	if(pListHead==NULL||k==0)
            return NULL;
        ListNode*pTail=pListHead,*pHead=pListHead;
        for(int i=1;i<k;++i)
        {
            if(pHead->next!=NULL)
                pHead=pHead->next;
            else
                return NULL;
        }
        while(pHead->next!=NULL)
        {
            pHead=pHead->next;
            pTail=pTail->next;
        }
        return pTail;
    }
};

发表于 2016-07-19 19:40:59 回复(9)
和时间赛跑头像 和时间赛跑 
 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)
黎离头像 黎离 
//递归简洁明了
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 回复(3)
努力编程头像 努力编程 
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 回复(5)
晓宇大美女~头像 晓宇大美女~ 
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 回复(10)
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 回复(2)
Java
Raymelo头像 Raymelo
思路：
定义快指针和慢指针。
快指针先走 k-1 步，到达第 k 个节点。
然后两指针同时齐步走，当快指针到达末尾时，慢指针在倒数第 k 个节点上。 
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k <= 0) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        for (int i = 1; i < k; i++) {
            if (fast.next == null) {
                return null;
            }
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

编辑于 2018-03-04 18:23:19 回复(3)
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)
牛客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)
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)
剑影头像 剑影 
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)
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
宸风头像 宸风 
//用栈的先进后出特性来做，测试通过
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)
虵乡遇故知头像 虵乡遇故知 

/*
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)
提交观点

问题信息

链表
难度：
1324条回答 93256浏览

热门推荐

通过挑战的用户

查看代码

悬赏试题

查看规则

相关试题

扫一扫，把题目装进口袋

牛客网，程序员必备求职神器

扫描二维码，进入QQ群

扫描二维码，关注牛客网公众号
  • 公司地址：北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式：010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号