Java输出链表倒数第k个节点

问题描述

输入一个链表，输出该链表中倒数第k个结点。(尾结点是倒数第一个)

结点定义如下：

public class ListNode {
  int val;
  ListNode next = null;

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

思路1：

先遍历链表，计算其长度length;
然后计算出倒数第k个结点就是正数第length - k + 1.
最后再遍历链表，找到所求结点
时间复杂度O(2n),需要遍历两次链表

代码如下：

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0){
      return null;
    }
    //直接遍历
    ListNode p = head;
    int length = 1;
    while(p.next != null){
      length++;
      p = p.next;
    }
    int index = length - k + 1;
    if(index <= 0){
      return null;
    }
    p = head;
    int num = 1;
    while(p.next != null && num < index){
      num++;
      p = p.next;
    }
    if(num < index){
      return null;
    }else{
      return p;
    }
  }

思路2：

期待只遍历链表一次就能得到。
设置两个指针，一个初始化指向第一个结点，第二个指向第k个结点。然后两个指针同步向后移动，当第二个指向尾结点时，第一个指针即指向了倒数第k个结点

代码：

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0){
      return null;
    }
    //直接遍历
    ListNode p = head;
    ListNode q = head;
    for(int i = 0; i < k-1; i++){
      if(q == null){
        return null;
      }
      q = q.next;
    }
    if(q == null){
      return null;
    }
    while(q.next != null){
      p = p.next;
      q = q.next;
    }
    return p;
  }

思路3：

将链表反转，那么原问题就变为求正数第k个结点。
然而这改变了原本的链表，且并不会比思路2更高效

链表反转：参考《Java语言实现反转链表代码示例》

总结

以上就是本文关于Java输出链表倒数第k个节点的全部内容，感兴趣的朋友可以继续参阅：Java编程删除链表中重复的节点问题解决思路及源码分享、Java编程实现从尾到头打印链表代码实例以及本站其他相关专题，如有不足之处，欢迎留言指出，小编一定及时更正，给大家更好的阅读体验和帮助，感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • Java编程删除链表中重复的节点问题解决思路及源码分享

    一. 题目 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针. 二. 例子 输入链表:1->2->3->3->4->4->5 处理后为:1->2->5 三. 思路 个人感觉这题关键是注意指针的指向,可以定义一个first对象(值为-1,主要用于返回操作后的链表),first.next指向head,定义一个last同样指向first(主要用于操作记录要删除节点的前一个节点),定义一个p指向head,指向当前节点.

  • Java数据结构之链表(动力节点之Java学院整理)

    Java数据结构之链表(动力节点之Java学院整理)

    单链表: insertFirst:在表头插入一个新的链接点,时间复杂度为O(1) deleteFirst:删除表头的链接点,时间复杂度为O(1) find:查找包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) remove:删除包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) public class LinkedList { private class Data{ private Object obj; private Data next =

  • Java输出链表倒数第k个节点

    问题描述 输入一个链表,输出该链表中倒数第k个结点.(尾结点是倒数第一个) 结点定义如下: public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } 思路1: 先遍历链表,计算其长度length; 然后计算出倒数第k个结点就是正数第length - k + 1. 最后再遍历链表,找到所求结点 时间复杂度O(2n),需要遍历两次链表 代码如下: public List

  • C语言实现输出链表中倒数第k个节点

    本文实例展示了C++实现输出链表中倒数第k个节点的方法,分享给大家供大家参考之用. 运行本文所述实例可实现输入一个单向链表,输出该链表中倒数第k个节点. 具体实现方法如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> using namespace std; int array[] = {5, 7, 6, 9, 11, 10, 8}; const int size = size

  • 如何利用Java输出链表中倒数第k个结点

    如何利用Java输出链表中倒数第k个结点

    目录 前言 问题描述 方法一 方法描述 动画演示 代码如下 方法二 方法描述 动画演示 代码如下 总结 前言 链表是一种数据结构,和数组同级.比如,Java中我们使用的ArrayList,其实现原理是数组.而LinkedList的实现原理就是链表了.链表在进行循环遍历时效率不高,但是插入和删除时优势明显 本文主要介绍的是输出链表中倒数第k个结点,下面来一起看看详细的介绍吧 问题描述 给你一个单链表,输出倒数第k个结点,如下图链表中,输出倒数第k个结点,比如 k = 2,输出5这个结点. 方法一

  • PHP获取链表中倒数第K个节点的方法

    本文实例讲述了PHP获取链表中倒数第K个节点的方法.分享给大家供大家参考,具体如下: 问题 输入一个链表,输出该链表中倒数第k个结点. 解决思路 注意这个题目是返回节点,而不是返回值.返回值的话可以用栈来存储.返回节点则不能这样做. 设置两个指针,先让第一个指针移动k-1次.然后两个指针同时移动,当第一个指针到达最后一个节点,第二个指针就在倒数第k个节点. 注意边界:K长度可能超出链表长度,所以当第一个指针的next为空时,返回null 实现代码 <?php /*class ListNode{

  • C++实现单链表删除倒数第k个节点的方法

    本文实例讲述了C++实现单链表删除倒数第k个节点的方法.分享给大家供大家参考,具体如下: 题目: 删除单链表中倒数第k个节点 解题思路及算法代码: 标尺法,定义两个指针指向链表头结点,先让一个走k步,然后两个指针同时开始走,当先走的指针走到末尾时,后走的指针指向的结点就是需要删除的结点. 单链表结构定义: typedef struct Node { int data; struct Node* next; }node, *pLinkedList; 删除倒数第K结点操作代码: //head表示头结

  • python实现单链表中删除倒数第K个节点的方法

    本文实例为大家分享了python实现单链表中删除倒数第K个节点的具体代码,供大家参考,具体内容如下 题目: 给定一个链表,删除其中倒数第k个节点. 代码: class LinkedListAlgorithms(object): def __init__(self): pass def rm_last_kth_node(self, k, linked_list): # 删除倒数第 K 个节点,针对单链表的 if linked_list.is_empty(): print 'The given li

  • python实现获取单向链表倒数第k个结点的值示例

    本文实例讲述了python实现获取单向链表倒数第k个结点的值.分享给大家供大家参考,具体如下: #初始化链表的结点 class Node(): def __init__(self,item): self.item = item self.next = None #传入头结点,获取整个链表的长度 def length(headNode): if headNode == None: return None count = 0 currentNode =headNode #尝试了一下带有环的链表,计算

  • C++实现LeetCode(19.移除链表倒数第N个节点)

    C++实现LeetCode(19.移除链表倒数第N个节点)

    [LeetCode] 19. Remove Nth Node From End of List 移除链表倒数第N个节点 Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the en

  • 找出链表倒数第n个节点元素的二个方法

    方法一:利用两个指针p,q,首先将q往链表尾部移动n位,然后再将p.q一起往后移,那么当q达到链表尾部时,p即指向链表的倒数第n个节点. 复制代码 代码如下: node* find_nth_to_last(node* head,int n) { if(head==NULL || n<1) return NULL; node*p,*q; p=q=head; while(q!=NULL && n--){ q=q->next; } if(n>=0) return NULL; w

  • C++解决输出链表中倒数k个结点的问题

    C++解决输出链表中倒数k个结点的问题

    目录 题目描述 示例 解题思路 测试代码 补充 题目描述 输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点. 如果该链表长度小于k,请返回一个长度为 0 的链表. 数据范围:0<=n<=10^5,0<=ai<=10^9,0<=k<=10^9 要求:空间复杂度O(n),时间复杂度O(n) 进阶:空间复杂度O(1),时间复杂度O(n) 例如输入{1,2,3,4,5},2时,对应的链表结构如下图所示: 其中蓝色部分为该链表的最后2个结点,所

随机推荐