首页 > 试题广场 >

链表中倒数第k个结点

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

输入

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

输出

{5}

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
推荐
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)

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

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

使用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)
# -*- 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)
//方法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)
//遍历二次
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)
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)