首页 > 试题广场 > 链表中倒数第k个结点
[编程题]链表中倒数第k个结点
输入一个链表,输出该链表中倒数第k个结点。

1194个回答

添加回答
推荐
最佳代码:Java代码,通过
   查看全部
编辑于 2015-08-25 17:44:14 回复(72)
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 回复(42)
时间复杂度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 回复(27)
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 回复(6)

明明是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 回复(10)
使用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 回复(8)
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)
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)
//递归简洁明了
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 回复(1)
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)
思路:
定义快指针和慢指针。
快指针先走 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)

设置两个指针 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)
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答案,感觉不是很好,都用了复杂的数据结构

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)
# -*- 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)
//用栈的先进后出特性来做,测试通过
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)
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)
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)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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

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