首页 > 试题广场 >

输出单向链表中倒数第k个结点

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

输入一个单向链表,输出该链表中倒数第k个结点,链表的倒数第1个结点为链表的尾指针。

链表结点定义如下:
struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};
正常返回倒数第k个结点指针,异常返回空指针.
要求:
(1)正序构建链表;
(2)构建后要忘记链表长度。
数据范围:链表长度满足 ,链表中数据满足

本题有多组样例输入。




输入描述:

输入说明
1 输入链表结点个数
2 输入链表的值
3 输入k的值



输出描述:

输出一个整数

示例1

输入

8
1 2 3 4 5 6 7 8
4

输出

5
#include<iostream>
#include<malloc.h>
using namespace std;
/*结构体定义*/
typedef struct listNode{
	int m_nKey;
	listNode* m_pNext;
}ListNode;

/*函数声明*/
ListNode* CreateList(int n);
int LengthOfList(ListNode* head);
ListNode* Return_Kth_Node_From_End(ListNode* head,int k);
void print(ListNode* head);

/*打印链表*/
void print(ListNode* head)
{
	ListNode* p=head;
	while(p!=NULL)
	{
		cout<<p->m_nKey<<" ";
		p=p->m_pNext;
	}
}

/*创建链表*/
ListNode* CreateList(int n)
{
	ListNode* head = NULL;
	if(n == 0)
	{
		return head;
	}
	else
	{
		head = (ListNode*)malloc(sizeof(ListNode));
		//head.m_pNext=NULL; 
		ListNode* p = head;
		ListNode* p1=NULL;
		for( int i = 1; i < n; i++ )
		{
			//p.m_pNext=NULL;
			p1 = (ListNode*)malloc(sizeof(ListNode));
			p->m_pNext = p1;
			//p.m_pNext = NULL;
			p=p1;
		}
		p->m_pNext=NULL;
		int num=0;
		p=head;
		for(int i = 0;i < n ; i++)
		{
			scanf("%d",&num);
			p->m_nKey=num;
			p=p->m_pNext;
		}
		return head;
	}
}

/*测量链表长度*/
int LengthOfList(ListNode* head)
{
	int len = 0;
	if (NULL == head )
	{
		return 0;
	}
	else
	{
		ListNode* p = head;
		while(p != NULL)
		{
			len = len + 1;
			p = p->m_pNext;
		}
		return len;
	}
}

/*返回倒数第k个节点*/
ListNode* Return_Kth_Node_From_End(ListNode* head,int k)
{
	ListNode* p = head;
	if(NULL == head)
	{
		return NULL;
	}
	else
	{
		int len=LengthOfList(head);
		//int k=0;
		if(k == len-1)
		{
			return head;
		}
		else if(k >= len-1 )
		{
			return NULL;
		}
		else
		{
			for(int i=1;i<(len-k);i++)
			{
				p=p->m_pNext;
			}
			return p;
		}
	}	
}

int main()
{
	int num=0,k=0;
	    while(cin>>num)
	    {
	    	ListNode* head = CreateList(num);	
			cin>>k;
			ListNode* p = Return_Kth_Node_From_End(head,k);
			cout<<p->m_nKey<<endl;
		}
	return 0;
}

发表于 2016-04-09 13:17:11 回复(0)
注释非常详细,简单易懂
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String len1 = "";
        while ((len1 = br.readLine()) !=null){
            String str1 = br.readLine();
            int kLen = Integer.parseInt(br.readLine());

            String[] strArr = str1.split(" ");
            int n = strArr.length;
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i){
                arr[i] = Integer.parseInt(strArr[i]);
            }
            //构造链表头节点
            ListNode head = new ListNode(arr[0]);
            //用另一个节点来遍历,以及一个指向头节点的节点
            ListNode first = head, current = new ListNode(-1, head);
            //构造链表
            ConstructNode(head, arr);
            //循环k次,以12345678  4举例,则此时first到了4的位置
            for (int i = 0; i < kLen; ++i){
                first = first.next;
            }
            //此时first会走到8之后,也就是5 6 7 8 null的位置,而current则会走-1 1 2 3 4
            // 的位置,此时不管是完成删除链表和读取链表都可以轻松完成
            while (first != null){
                first = first.next;
                current = current.next;
            }
            System.out.println(current.next.val);
        }
    }
    
        /**
     * 构造链表
     * @param head
     * @param arr
     */
    public static void ConstructNode(ListNode head, int[] arr){
        for (int i = 1; i < arr.length; ++i){
            ListNode listNode = new ListNode(arr[i]);
            head.next = listNode;
            head = head.next;
        }
    }
}

class ListNode{
    int val;
    ListNode next;

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

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


发表于 2022-08-04 15:29:00 回复(0)
力扣原题,不过要会自己造链表
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
        int len = sc.nextInt();
        ListNode head = new ListNode(-1);
        ListNode temp = head;
        for(int i = 0;i < len;i++){
            int val = sc.nextInt();
            temp.next = new ListNode(val);
            temp = temp.next;
        }
        int num = sc.nextInt();
        for(int j = 0;j < len - num + 1;j++){
            head = head.next;
        }
        System.out.println(head.val);
    }
    }
}

 class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }


发表于 2022-05-30 15:39:15 回复(0)
标准的双指针解法
#include<iostream>
using namespace std;
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x,ListNode* next):val(x),next(next){}
};
ListNode* findKthFromEnd(ListNode*& head,int k){
    auto dummyHead=new ListNode(0,head);
    auto first=dummyHead;
    auto second=head;
    while(k--) second=second->next;
    while(second){
        first=first->next;
        second=second->next;
    }
    return first->next;
}
int main(){
    int n, val, Kth;
    while(cin>>n){    //题中说明有多组样例输入
        cin>>val;
        auto head=new ListNode(val,NULL);
        auto cur=head;
        --n;
        while(n--){
            cin>>val;
            auto node=new ListNode(val,NULL);
            cur->next=node;
            cur=cur->next;
        }
        cin>>Kth;
        if(Kth==0) cout<<0<<endl;
        else{
            auto target=findKthFromEnd(head, Kth);
            if(target) cout<<target->val<<endl;
        }
    }
    return 0;
}


发表于 2022-04-01 20:47:37 回复(0)
try:
    while True:
        n=input()
        aa=input().split(' ')
        bb=int(input())
        if bb>int(n) or bb<1:
            print('0')
        else:
            print(aa[-bb])
except:
    pass
发表于 2022-03-11 10:50:30 回复(0)
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

struct ListNode {
  int val;
  ListNode* next;
  ListNode(int _val) : val(_val), next(nullptr) {}
};

int main(const int argc, const char* const argv[]) {
  int n, val, k;
  ListNode *head, *tail, *slow, *fast;
  while (scanf("%d", &n) != EOF) {
    head = tail = nullptr;
    while (n--) {
      cin >> val;
      if (!head)
        head = tail = new ListNode(val);
      else
        tail = tail->next = new ListNode(val);
    }
    cin >> k;
    if (!k) {
      cout << '0' << endl;
      continue;
    }
    slow = fast = head;
    while (k--) fast = fast->next;
    while (fast) slow = slow->next, fast = fast->next;
    cout << slow->val << endl;
  }
  
  return 0;
}

发表于 2021-08-20 18:46:05 回复(0)
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext()) {

            int[] arr = new int[scanner.nextInt() + 1];

            for (int i = 0; i < arr.length - 1; i++) {
                arr[i] = scanner.nextInt();
            }

            System.out.println(arr[arr.length - scanner.nextInt() - 1]);

        }

    }

}

发表于 2021-07-21 14:50:57 回复(0)
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            ListNode head=new ListNode(0);
            ListNode node=head;
            int n=in.nextInt();
            for(int i=0;i<n;i++){
                node.next=new ListNode(in.nextInt());
                node=node.next;
            }
            int k=in.nextInt();
            int num=last(head,k);
            System.out.println(num);
            
        }
        in.close();
    }
    public static int last(ListNode head,int k){
        int t=0;
        ListNode nx=head,last1=head;
        while(nx!=null){
            t++;
            nx=nx.next;
        }
        int m=t-k;
        if(t==k&&t>0){
            return head.val;
        }
        if(k>t||k<=0){
            return 0;
        }
        for(int i=0;i<m;i++){
            last1=last1.next;
        }
        return last1.val;
    }
}
class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}

发表于 2021-02-23 14:41:34 回复(0)
说实话,最后一个用理没通过,之后输出空指针就通过了,有点懵!
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
struct ListNode
{
    int m_nkey;
    ListNode * m_pNext;
};

struct ListNode * test(int N)
{
       struct ListNode* headNode=new ListNode();
       struct ListNode* tmpNode=headNode;
        tmpNode->m_pNext=NULL;
        for(int i=0;i<N;i++)
        {
            int key;
            cin>>key;
            struct ListNode* lNode=new ListNode();
            lNode->m_nkey=key;
            lNode->m_pNext=tmpNode->m_pNext;
            tmpNode->m_pNext=lNode;
            tmpNode=lNode;
        }
        int k=0;
        cin>>k;
        if(k==0)
            return NULL;
        else
        {
            tmpNode=headNode;
            for(int i=N-k;i>=0;i--)
            {
                tmpNode=tmpNode->m_pNext;
            }
            return tmpNode;
        }
}
int main()
{
    int N=0;
    while(cin>>N)
    {
        auto p=test(N);
       if(p!=NULL)
       {
           cout<<p->m_nkey<<endl;
       }
        else
            cout<<p<<endl;
    }

    return 0;
}


发表于 2021-02-20 14:51:48 回复(0)
Java:
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            Node head = null;
            int n = sc.nextInt();
            for (int i = 0; i < n; i++) {
                int val = sc.nextInt();
                Node node = new Node();
                node.next = head;
                node.val = val;
                head = node;
            }
            int k = sc.nextInt();
            if (k <= 0 || k >= n) {
                System.out.println(0);
                continue;
            }
            Node p = head, q = head;
            for (int i = 0; i < n - k + 1; i++) {
                p = p.next;
            }
            while (p != null) {
                p = p.next;
                q = q.next;
            }
            System.out.println(q.val);
        }
    }

    private static class Node {
        private Node next;
        private int val;
    }
}

编辑于 2021-01-30 18:12:22 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            String num = scanner.nextLine();
            List<String> linkedList = new LinkedList<>(Arrays.asList(scanner.nextLine().split(" ")));
            Collections.reverse(linkedList);
            String indexReverse = scanner.nextLine();
            if (Integer.parseInt(indexReverse) > 0){
                System.out.println(linkedList.get(Integer.parseInt(indexReverse)-1));
            }else{
                System.out.println("0");
            }
        }
    }
}

发表于 2021-01-11 13:28:49 回复(0)
class LNode:
    def __init__(self, elem, _next = None):
        self.elem = elem
        self.next = _next
        
class LList:
    def __init__(self):
        self._head = None
        
    def prepend(self, elem):
        self._head = LNode(elem, self._head)
        
    def search(self, k):
        p = self._head
        while p is not None and k > 1:
            k -= 1
            p = p.next
        if k == 1:
            print(p.elem)
            
    def length(self):
        p = self._head
        l = 0
        while p is not None:
            l += 1
            p = p.next
        return l
            
    def append(self, elem):
        if self._head is None:
            self._head = LNode(elem)
            return
        p = self._head
        while p.next is not None:
            p = p.next
        p.next = LNode(elem)

while True:
    try:
        L = int(input())
        N = [int(i) for i in input().split()]
        P = int(input())
        A = LList()
        for i in N:
            A.append(i)
        if P == 0:
            print(0)
        else:
            k = A.length() - P + 1
            A.search(k)
    except:
        break
        定义了类,倒序就是长度-倒序号+1,这样在搜索就能够搜索到位置,为了避免位置出错,下边应以0开始,而且,特殊情况是1个元素,索引为0

发表于 2020-08-11 16:45:05 回复(0)
#include <bits/stdc++.h>
using namespace std;
struct ListNode{
    int key;
    ListNode* pNext;
};
ListNode* createList(vector<int>& vec){
    ListNode* list = new ListNode{vec[0],NULL},*lastNode=list;
    for(int i=1;i<vec.size();++i){
        ListNode* node = new ListNode{vec[i],NULL};
        lastNode->pNext=node;
        lastNode = node;
    }
    return list;
}
int findKeyByRIndex(ListNode* list,int listSize,int k){
    if(k==0) return 0;
    ListNode* current = list;
    for(int i=0;i<(listSize-k);++i)
        current = current->pNext;
    return current->key;
}
int main(){
    int n,k;
    while(cin>>n){
        vector<int> vec(n);
        for(int i=0;i<vec.size();++i) cin>>vec[i];
        cin>>k;
        ListNode* list = createList(vec);
        cout << findKeyByRIndex(list,n,k) << endl;
    }
}
        😑
发表于 2020-06-27 12:27:08 回复(0)
#include<stdio.h>
(737)#include<stdlib.h>
#include<string.h>
struct ListNode
{
	int       data;
	struct ListNode* m_pNext;
};
struct ListNode* creat_node(int data) {
	struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (p == NULL) {
		printf("malloc error.\n");
		return NULL;
	}
	memset(p, 0, sizeof(struct ListNode));
	p->data = data;
	p->m_pNext = NULL;
	return p;
}
void insert(struct ListNode* pH, struct ListNode* new) {
	struct ListNode* p = pH;
	while (p->m_pNext != NULL) {
		p = p->m_pNext;
	}
	p->m_pNext =new;
	new->m_pNext = NULL;
}
int main() {
	int num = 0,delete = 0;
	
	while (scanf("%d", &num) != EOF) {
		int data1[10000] = { 0 }, data = 0;
		for (int i = 0; i < num; i++) {
			scanf("%d", &data1[i]);
		}
		scanf("%d", &data);
		struct ListNode* pHeader = creat_node(data);
		struct ListNode* p = NULL;
		for (int i = 0; i < num; i++) {
			insert(pHeader, creat_node(data1[i]));
		}
		p = pHeader;
		if (data >= 1 && data <=num) {
			for (int i = 0; i < num - data + 1; i++) {
				p = p->m_pNext;
			}
			printf("%d\n", p->data);
		}
		else {
			printf("0\n");
		}
	}
	return 0;
}
百分之九十的正确应该是没有对数组的范围进行判断,判断一下就好了,对于数组溢出的情况输出为0,可以通过检查错误的用例测试得到。
case通过率为90.00%

用例:
1
8108
0

对应输出应该为:

0
发表于 2020-04-17 10:45:36 回复(0)
#include <stdio.h>

typedef struct Node{
    int data;
    struct Node * Next;
}Node,*ListNode;

void insert(ListNode *L,int n)	//头插法 
{
    ListNode p;
    int i,e;
	(*L) = (ListNode)malloc(sizeof(Node));	//头结点 
	(*L)->Next = NULL; 
	for(i=0; i<n; i++)
	{
		scanf("%d",&e);
		p = (ListNode)malloc(sizeof(Node));
		p->data = e;
		p->Next = (*L)->Next;
		(*L)->Next = p;
	}	
}

int main()
{
    int i,n,d;
    while(scanf("%d",&n) != EOF )
    {
    	ListNode L,P;
  	 	insert(&L,n);
        scanf("%d",&d);  
		for(i=0; i<d; i++) 
			L =	L->Next;
		printf("%d\n",L->data);
    }
    return 0;
}

发表于 2020-04-07 20:08:17 回复(1)
#include<vector>
(721)#include<string>
#include<iostream>
(720)#include<stdlib.h>
#include<algorithm>
using namespace std;

typedef struct Listnode
{
	int num;
	Listnode * Front_ptr;
	Listnode * Back_ptr;
	Listnode(int x) : num(x), Front_ptr(NULL), Back_ptr(NULL) {}
};

Listnode *  Create_linked_list(int &num)
{	
	// 创建节点数为 num 的链表
	Listnode * head_ptr = new Listnode(-1);
	Listnode * prev_ptr = head_ptr;
	Listnode * cur_ptr;
	for (int i = 0; i < num; i++)
	{
		cur_ptr = (Listnode *)malloc(sizeof(Listnode));
		prev_ptr->Back_ptr = cur_ptr;
		cur_ptr->Front_ptr = prev_ptr;
		prev_ptr = cur_ptr;
	}
	prev_ptr->Back_ptr = NULL;
	return head_ptr;
}

int main()
{
	int num;
	while (cin >>num)
	{
		// 创建链表
		Listnode * head_ptr = Create_linked_list(num);

		// 往链表中保存数据
		Listnode * temp_ptr = head_ptr->Back_ptr;
		for (int i = 0; i < num; i++)
		{
			cin >> temp_ptr->num;
			temp_ptr = temp_ptr->Back_ptr;
		}

		// 找到链表倒数第k个节点的数
		int node_index;
		cin >> node_index;
		if (node_index > num || node_index == 0)
		{
			cout << 0 << endl;
		}
		else
		{
			temp_ptr = head_ptr;
			for (int i = 0; i <= num - node_index; i++)
			{
				temp_ptr = temp_ptr->Back_ptr;
			}
			cout << temp_ptr->num << endl;
		}
	}
	system("pause");
	return 0;
}

发表于 2020-03-10 17:35:05 回复(0)
主要是计算,顺序遍历的次数,总数-倒数第几个+1等于顺序的次数。
还有倒数第0个是的结果,完全是测试用例试探出来的,题目并没提示这种情况输出0

如果s
import sys

for line in sys.stdin:
    num = eval(line.strip())
    Link = input().strip().split()
    id =  eval(input().strip())
    # 倒数第0个结点返回0,完全是测试用例试探出来的,真没搞懂,题目也没这要求呀
    if 0 == id:
        print(0)
    elif num-id <= len(Link):
        print(Link[num-id])
    else:
        print(None)

c++实现时,有2个注意的地方:
1.头结点必须是实例化内存的节点,不能写成空指针,ListNode* head = NULL;
2.输出格式必须带换行,写成cout << 0;会出现测试用例通不过
#include<iostream>
using namespace std;
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(NULL) {}
};

void createLink(ListNode* &head, int size) {
    ListNode* p = head;
    ListNode* s = NULL;
    for(int i = 0; i < size; ++i) {
        int val;
        cin >> val;
        //cout << val << endl;
        s = new ListNode(val);
        p->next = s;
        p = p->next;
    }
}
void visitLink(ListNode* head, int num) {
    int idx;
    cin >> idx;
    if(0 == idx) {
        // 又是格式错误,必须带换行,写成cout << 0;会出现测试用例通不过
        cout << 0 << endl;
        return ;
    }
    ListNode* p = NULL;
    int cnt;
    for(cnt = 0, p = head->next; cnt < num-idx; p = p->next, ++cnt) {}
    cout << p->val << endl;
}


int main() {
    int num;
    while(cin >> num) {
        // 头结点必须是实例化内存的节点,不能写成空指针,ListNode* head = NULL;
        ListNode* head = new ListNode(-1);
        createLink(head, num);
        visitLink(head, num);
    }
    return 0;
}



编辑于 2020-03-08 15:13:09 回复(0)
class Node(object):
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    def __init__(self,node=None):
        self._head = node

    def append(self,item):
        node = Node(item)
        if not self._head:
            self._head = node
        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.next = node

    def length(self):
        count = 0
        cur = self._head
        while cur:
            count += 1
            cur = cur.next
        return count

    def search(self,item):
        if not self._head:
            return
        else:
            cur = self._head
            count = 0
            while cur:
                if item <= 0&nbs***bsp;item > self.length():
                    return 0
                else:
                    if count == self.length() - item:
                        return cur.elem
                    count += 1
                    cur = cur.next
            return 0
while True:
    try:
        ll = SingleLinkList()
        a,b,c = int(input()),list(map(int,input().split())),int(input())
        for i in b:
            ll.append(i)
        print(ll.search(c))
    except:
        break

编辑于 2020-02-29 13:47:40 回复(2)
别的不会,只会偷鸡
#include<iostream>
using namespace std;

int main(){
	int _num;
	int _dnum;
	while (cin >> _num) {
		int* _link = new int[_num];
		for (int i = 0; i < _num; i++) {
			cin >> _link[i];
		}
		cin >> _dnum;
		cout << _link[_num - _dnum] << endl;
	}
}

发表于 2020-02-25 18:55:58 回复(1)
边界条件是什么鬼,不看讨论的回答还真不知道,k是0的时候直接输出0就对了
#include <iostream>
using namespace std;
struct ListNode
{
    int Key;
    ListNode* next;
    ListNode(int v)
    {
        Key = v;
        next = NULL;
    }
};
int FindLen(ListNode* phead)
{
    int len = 0;
    while (phead != NULL)
    {
        len++;
        phead = phead->next;
    }
    return len;
}
ListNode* FindKthToTail(ListNode* phead, unsigned k)
{
    ListNode* res = phead;
    int n = FindLen(phead);
    n = n - k + 1; //正数第n个
    for (int i = 1; i < n; ++i)
    {
        res = res->next;
    }
    return res;
}
void CreateList(ListNode*& head, int n)
{
    int v;
    cin >> v;
    head = new ListNode(v);
    ListNode* p = head;
    for (int i = 1; i < n; ++i)
    {
        cin >> v;
        ListNode* temp = new ListNode(v);
        p->next = temp;
        p = temp;
    }
}
int main()
{
    int num;
    while (cin >> num)
    {
        ListNode* head;
        CreateList(head, num);
        int k;
        cin >> k;
        if(k==0)
        {
            cout << 0 << endl;
            continue;
        }
        else
        {
            ListNode* res = FindKthToTail(head, k);
            cout << res->Key << endl;
        }
    }
    return 0;
}


发表于 2020-02-04 22:46:06 回复(0)