输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int val;
ListNode* m_pNext;
}; 正常返回倒数第k个结点指针。
[编程题]输出单向链表中倒数第k个结点
- 热度指数：227319 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
每一个测试用例会有多组。每一组的测试用例格式如下：第一行输入链表结点个数，
第二行输入长度为，表示链表的每一项，
第三行输入的值，
输出描述:
每一组，输出倒数第k个结点的值
示例1
输入
3 1 2 3 1 8 1 2 3 4 5 6 7 8 4
输出
3 5
// 设置两个指针，一个初始化指向第一个结点，第二个指向第k个结点。然后两个指针同步向后移动，当第二个指向尾结点时，第一个指针即指向了倒数第k个结点。
// 尾插法
// 注意类名必须为 Main, 不要有任何 package xxx 信息
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = Integer.parseInt(sc.next());
ListNode head = new ListNode(-1);
ListNode temp = head;
//生成链表
for (int i = 0; i < n; i++) {
ListNode node = new ListNode(sc.nextInt());
temp.next = node;
temp = temp.next;
}
int k = Integer.parseInt(sc.next());
//使用快慢指针
if (getKthFromEnd(head.next, k) != null) {
System.out.println(getKthFromEnd(head.next, k).val);
} else {
System.out.println(0);
}
}
}
//通过快慢指针搜索
public static ListNode getKthFromEnd(ListNode head, int k) {
if (head == null) return null;
ListNode fast = head, slow = head;
//快指针先走k步
for (int i = 0; i < k; i++) {
if (fast == null) return fast;
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
class ListNode {
ListNode next;
int val;
ListNode(int val) {
this.val = val;
next = null;
}
}
发表于 2024-09-12 15:36:06
回复(0)
import java.io.*;
//自定义链表节点类
class ListNode {
int num;
ListNode next;
public ListNode() {}
public ListNode(int l, ListNode n) {
this.num = l;
this.next = n;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String str = null;
while ((str=bf.readLine()) != null) {
//获取原始输入
int len = Integer.parseInt(str);
String[] num = bf.readLine().split(" ");
int want = Integer.parseInt(bf.readLine());
//创建链表头节点
ListNode ls = new ListNode();
//头插法将新节点插入链表头
for (int i = 0; i < len; i++) {
ListNode newC = new ListNode(Integer.parseInt(num[i]), ls);
//更新头节点
ls = newC;
}
//从头开始遍历链表直至满足条件
while (ls != null && want != 1) {
ls = ls.next;
want--;
}
//输出对应节点
System.out.println(ls.num);
}
}
}
发表于 2024-09-05 10:59:31
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int len = in.nextInt();
in.nextLine();
LinkedList<Object> list = new LinkedList<>();
for (int i = 0; i < len; i++) {
list.add(in.nextInt());
}
in.nextLine();
int index = in.nextInt();
System.out.println(list.get(len - index));
}
}
}
发表于 2024-07-06 21:21:32
回复(0)
要什么自行车
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) {
out(in);
}
}
private static void out(Scanner in) {
int len = in.nextInt();
List<Integer> li = new ArrayList();
while (li.size() < len) { // 注意 while 处理多个 case
li.add(in.nextInt());
}
int val = in.nextInt();
if (val <= len) {
System.out.println(li.get(len - val));
}
}
}
发表于 2024-04-08 13:00:41
回复(1)
采用尾插法构建链表，正数第length-k+1个节点就是倒数第k个！
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int num = sc.nextInt();
//构建带头节点的链表
ListNode head = new ListNode();
ListNode temp = head;//head不移动，利用中间变量来遍历
for(int i = 0;i < num;i++){
int val = sc.nextInt();
ListNode node = new ListNode(val,temp.next);
temp.next = node;//前一个节点的尾指向后一个节点
temp = temp.next;//temp后移
}
int k = sc.nextInt();
//查找倒数第K个节点
if(getnum(head,k) != null){
System.out.println(getnum(head,k).value);
}
else{
System.out.println(0);
}
}
sc.close();
}
public static ListNode getnum(ListNode head,int k){
int length = 0;
ListNode node = head.next;//从第一个节点开始计算长度
//计算链表长度
while(node != null){
length++;
node = node.next;
}
//查找倒数第K个节点
if(length == 0 || k > length){//异常返回空指针
return null;
}
node = head; //因为底下的for循环一进去i=0时候就已经node = node.next;把第一个节点的值给了node,所以此处不要写head.next
for(int i = 0;i < length - k + 1;i++){//从头节点开始，正数length-k+1就是倒数第K个节点
node = node.next;
}
return node;
}
}
class ListNode{
int value;
ListNode next;
public ListNode(){ //空参构造器
}
public ListNode(int value,ListNode next){ //全参构造器
this.value = value;
this.next = next;
}
}
发表于 2024-01-12 19:04:00
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int nodeNum = in.nextInt();
//创建头指针和操作指针p，默认复制头指针给p，后面还会用到头指针所以需要两个指针
ListNode headNode = new ListNode();
ListNode p = headNode;
for(int i = 0; i < nodeNum; i++){
ListNode untilNode;
untilNode = new ListNode(in.nextInt(),null);
p.next = untilNode;
p = untilNode;
}
int key = in.nextInt();
ListNode newNode = null;
for(int j = 0; j <= nodeNum-key; j++){
newNode = headNode.next;
headNode = newNode;
}
System.out.println(newNode.value);
}
}
}
class ListNode{
int value;
ListNode next;
public ListNode(){}
public ListNode(int value,ListNode next){
this.value = value;
this.next = next;
}
}这道题主要考察头插法
发表于 2023-12-15 12:11:51
回复(0)
import java.util.Scanner;
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
next = null;
}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
ListNode head = new ListNode(in.nextInt());
ListNode p = head;
for (int i = 1; i < n; i++) {
ListNode node = new ListNode(in.nextInt());
p.next = node;
p = node;
}
int k = in.nextInt();
p = head;
ListNode q = head;
while (k-- > 1) {
p = p.next;
}
//如果p为空说明出现异常,否则p走到尾部，q就是倒数第k个节点
while (p.next != null) {
p = p.next;
q = q.next;
}
System.out.println(q.val);
}
}
}
发表于 2023-11-25 00:48:37
回复(0)
假如我用数组求解，阁下又该如何应对呢？
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while(in.hasNextInt()){
int n = in.nextInt();
int[] num = new int[n];
for(int i = 0;i < n;i ++){
num[i] = in.nextInt();
}
int m = in.nextInt();
if(m > n){
return;
}else{
System.out.println(num[n - m]);
}
}
}
}
发表于 2023-10-25 23:59:55
回复(1)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
ListNode head=getList(in);
int k=in.nextInt();
System.out.println(findReverseKth(head,k).m_nKey);
}
}
private static ListNode findReverseKth(ListNode head,int k){
ListNode curr=head;
int n=0;
while(curr!=null){
curr=curr.m_pNext;
n++;
}
int index=n-k;
if(index>=0){
curr=head;
for(int i=0;i<index;i++){
curr=curr.m_pNext;
}
return curr;
}
return null;
}
private static ListNode getList(Scanner in){
int n=in.nextInt();
ListNode headPrev=new ListNode();
ListNode curr=headPrev;
for(int i=0;i<n;i++){
curr.m_pNext=new ListNode(in.nextInt());
curr=curr.m_pNext;
}
return headPrev.m_pNext;
}
static class ListNode{
int m_nKey;
ListNode m_pNext;
public ListNode(){
m_pNext=null;
}
public ListNode(int key){
m_nKey=key;
m_pNext=null;
}
}
}
发表于 2023-09-10 20:37:10
回复(0)
while(in.hasNextInt()){
int n=in.nextInt();
List<Integer> ls= new LinkedList<>();
for(int i=0;i<n;i++){
ls.add(in.nextInt());
}
int index=in.nextInt();
System.out.println(ls.get(ls.size()-index));
}
发表于 2023-06-08 10:43:38
回复(1)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n=in.nextInt();
//用list来构造链表，效果相同，不用其长度
ArrayList<Integer> list=new ArrayList<>();
for(int i=0;i<n;i++){
list.add(in.nextInt());
}
int k=in.nextInt();
int num=0;
int left=0;
int right=0;
//忘记链表长度
while(true){
//相当于right节点==null的效果
if(right==list.size()-1){
//当right节点null时，将left节点位置的值输出
num=list.get(left);
break;
}
//维护位置
if(right-left!=k-1){
right++;
}else{
right++;
left++;
}
}
System.out.println(num);
}
}
}
发表于 2023-05-31 10:09:07
回复(0)
import java.io.*;
//创建节点类
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
next = null;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
int n = Integer.parseInt(str);
String[] strArr = br.readLine().trim().split(" ");
int k = Integer.parseInt(br.readLine());
//创建第首节点，不带头节点（因为该首节点数据区是有值，带头节点的链表含有一个数据区为空的节点用于指向首节点）
ListNode head = new ListNode(Integer.parseInt(strArr[0]));
//创建临时节点，指向首节点
ListNode temp = head;
//创建链表
for (int i = 1; i < n; i++) {
ListNode Node = new ListNode(Integer.parseInt(strArr[i]));
temp.next = Node;
temp = temp.next;
}
//直接输出第k个几点的值
System.out.println(getNodeFromEnd(head, k).val);
}
}
//题目要求构建后要忘记链表长度，即不让用main方法中获得的n，所以需要重新获得链表的长度
private static ListNode getNodeFromEnd(ListNode head, int k) {
//如果head.next == null，则链表只有一个节点，即只有head，题目已经规定链表长度为1到1000，所以不可能为空
if (head.next == null) return head;
int num = 0;
ListNode temp = head;
//temp != null说明已经统计完所有节点
while (temp != null) {
num++;
temp = temp.next;
}
temp = head;
//获取倒数第k个节点
for (int i = 1; i <= num - k; i++) {
temp = temp.next;
}
return temp;
}
}
发表于 2023-05-12 20:34:11
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int a = in.nextInt();
LinkedNode list = new LinkedNode();
//循环插入元素
for (int i = 0; i < a; i++) {
int val = in.nextInt();
list.insert(val);
}
int num = in.nextInt();
//获取倒数第k个元素
System.out.println(list.search(num));
}
}
}
class LinkedNode {
Node head;
class Node {
int val;
Node next;
Node(int val) {
this.val = val;
}
}
//正序构建链表(尾插法)
public void insert(int val) {
Node newNode = new Node(val);
if (head == null) {
head = newNode;
} else {
Node cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
}
}
//逆序遍历时无需通过链表长度
public int search(int num) {
Node right = head;
Node left = head;
int i = 0;
while (right.next != null) {
i++;
if (i >= num) {
left = left.next;
}
right = right.next;
}
return left.val;
}
}
发表于 2023-04-09 20:31:33
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int length = scanner.nextInt();
int headVal = scanner.nextInt();
ListNode header = new ListNode(headVal, null);
ListNode temp = header;
for (int i = 0; i < length - 1; i++) {
int value = scanner.nextInt();
ListNode node = new ListNode(value,null );
temp.next = node;
temp = node;
}
int k = scanner.nextInt();
//ListNode 头结点为header
ListNode cur = header;
for (int i = 0; i < k - 1; i++) {
if (cur.next == null)
return;
cur = cur.next;
}
ListNode result = header;
while (cur.next != null) {
cur = cur.next;
result = result.next;
}
System.out.println(result.val);
}
}
static class ListNode {
int val;
ListNode next = null;
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}
发表于 2023-03-11 13:46:00
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int size = in.nextInt();
ListNode dummy = new ListNode(-1, null);
ListNode curr = dummy;
for (int i = 0; i < size; i++) {
int x1 = in.nextInt();
curr.next = new ListNode(x1, null);
curr = curr.next;
}
int k = in.nextInt();
ListNode p = dummy, q = dummy;
for (int i = 0; i < k; i++) {
p = p.next;
}
while (p != null) {
p = p.next;
q = q.next;
}
System.out.println(q.val);
}
in.close();
}
}
class ListNode {
int val;
ListNode next;
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
发表于 2023-03-02 13:49:49
回复(0)
import java.io.*;//使用LinkedList集合实现数据以链表形式添加存储和查询
import java.util.LinkedList;
import java.util.List;
/**
用到方法：Integer.parseInt(str);s.readLine().split(" ");List<Object> list = new LinkedList<>();list.add(arr[i]);list.get(n - k)
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
int n;
String str;
while((str=s.readLine())!=null){//多组输入
n = Integer.parseInt(str);
String[] arr = s.readLine().split(" ");
int k = Integer.parseInt(s.readLine());
List<Object> list = new LinkedList<>();
for (int i = 0; i < arr.length; i++) {
list.add(arr[i]);
}
System.out.println(list.get(n - k));
}
}
}
发表于 2023-01-21 14:59:04
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int len = in.nextInt();
int[] data = new int[len];
for (int i = 0; i < len; i++) {
data[i] = in.nextInt();
}
int pos = in.nextInt();
int lastPos = len - pos;
System.out.println(data[lastPos]);
}
}
}
发表于 2022-12-08 18:01:04
回复(0)
我出息了
import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;
public class Main {
public static ListNode makeList(int [] nums){
if(nums.length==1)
return new ListNode(nums[0]);
ListNode head = new ListNode(0);
ListNode cur = head;
for(int k =1;k<nums.length;k++){
ListNode ln = new ListNode(nums[k]);
cur.next = ln;
cur = cur.next;
}
return head;
}
public static void main(String[] args) throws IOException{
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int n = scan.nextInt();
int [] nums = new int [n];
for(int i=0;i<n;i++){
nums[i] = scan.nextInt();
}
int k = scan.nextInt();
ListNode lit = makeList(nums);
ListNode fast = lit;
ListNode slow = lit;
// int i=1;
// while (i<k){
// fast=fast.next;
// i++;
// }
for(int i=1;i<k;i++){
fast=fast.next;
}
while (fast.next!=null){
fast=fast.next;
slow=slow.next;
}
System.out.println(slow.value) ;
}
}
}
class ListNode
{
int value;
ListNode next;
ListNode(int value){
this.value =value;
this.next = null;
}
};
发表于 2022-08-30 09:57:10
回复(0)
老老实实的正向构建链表+快慢指针访问倒数第k个节点
/**
* @author YXQ
* @create 2022/8/26 16:51
*/
import java.util.Scanner;
/**
* 输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。
* 正常返回倒数第k个结点指针，异常返回空指针.
* 要求：
* (1)正序构建链表;
* (2)构建后要忘记链表长度。
*
* 输入描述：
* 输入说明
* 1 输入链表结点个数
* 2 输入链表的值
* 3 输入k的值
*
* 输出描述：
* 输出一个整数
*/
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] nums=new int[n];
for(int i=0;i<n;i++)nums[i]=sc.nextInt();
int k=sc.nextInt();
ListNode head=makeList(nums);
ListNode kNode=printKNode(head,k);
System.out.println(kNode.val);
}
/**
* 快慢指针找到第k个节点
* @param head
* @param k
* @return
*/
public static ListNode printKNode(ListNode head,int k){
ListNode slow=head;
ListNode fast=head;
int i=1;
while (i<k){
fast=fast.next;
i++;
}
while (fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
/**
* 构建链表
* @param nums
* @return
*/
public static ListNode makeList(int[] nums){
if(nums.length==1)return new ListNode(nums[0]);
ListNode head=new ListNode(nums[0]);
ListNode cur=head;
for(int i=1;i<nums.length;i++){
cur.next=new ListNode(nums[i]);
cur=cur.next;
}
return head;
}
}
/**
* 链表的结点类
*/
class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val=val;
this.next=null;
}
}
发表于 2022-08-26 17:50:53
回复(2)
问题信息
难度：
78条回答
2236收藏
44794浏览
通过挑战的用户
查看代码-
2022-12-17 11:53:31 -
2022-10-27 18:28:26 -
2022-10-10 21:39:13
-
2022-10-10 11:22:33
-
2022-09-22 20:38:57
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
