找出链表倒数第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; while(p!=NULL && q!=NULL){ p=p->next; q=q->next; } return p; }

方法二:可以先计算出节点个数,即从头到尾遍历一次链表,得到个数m,那么倒数第n个元素也即第m-n+1个元素.与方法一是同样的思维,只是具体操作方式不同,代码略.
JAVA代码:


代码如下:

LinkedListNode nthToLast(LinkedListNode head, int n) { if (head == null || n < 1) { return null; } LinkedListNode p1 = head; LinkedListNode p2 = head; for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead if (p2 == null) { return null; // not found since list size < n } p2 = p2.next; } while (p2.next != null) { p1 = p1.next; p2 = p2.next; } return p1; }

赞 (0)

相关推荐

  • Linux内核链表实现过程

    关于双链表实现,一般教科书上定义一个双向链表节点的方法如下: 复制代码 代码如下: struct list_node{stuct list_node *pre;stuct list_node *next;ElemType data; } 即一个链表节点包含:一个指向前向节点的指针.一个指向后续节点的指针,以及数据域共三部分.但查看linux内核代码中的list实现时,会发现其与教科书上的方法有很大的差别.来看看linux是如何实现双链表.双链表节点定义 复制代码 代码如下: struct lis

  • C++中单链表的建立与基本操作

    C++中单链表的建立与基本操作

    准备数据 准备在链表操作中需要用到的变量及数据结构 示例代码如下: 复制代码 代码如下: struct Data   //数据结点类型 { string key;  //关键字  string name; int age;};struct CLType  //定义链表结构 { Data nodeData; Data *nextNode;}; 定义了链表数据元素的类型Data以及链表的数据结构CLType.结点的具体数据保存在一个结构Data中,而指针nextNode用来指向下一个结点. 我们可以

  • java单向链表的实现实例

    上代码喽~ 复制代码 代码如下: package ncu.com.app.chatpter_5; import java.util.Random; //结点类class Node { Object data; Node next; }//操作类class ListNode{ public Node first;  public int size;  public ListNode(){  first = null;  size = 0; } public void insertNode(Obje

  • 找出链表倒数第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

  • PHP实现找出链表中环的入口节点

    本文实例讲述了PHP实现找出链表中环的入口节点.分享给大家供大家参考,具体如下: 问题 一个链表中包含环,请找出该链表的环的入口结点. 解决思路 第一步,找环中相汇点.分别用p1,p2指向链表头部,p1每次走一步,p2每次走二步,直到p1==p2找到在环中的相汇点. 第二步,找环的入口.接上步,当p1==p2时,p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数,再让p2指向链表头部,p1位置不变,p1,p

  • 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++实现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

  • Python cookbook(数据结构与算法)找出序列中出现次数最多的元素算法示例

    本文实例讲述了Python找出序列中出现次数最多的元素.分享给大家供大家参考,具体如下: 问题:找出一个元素序列中出现次数最多的元素是什么 解决方案:collections模块中的Counter类正是为此类问题所设计的.它的一个非常方便的most_common()方法直接告诉你答案. # Determine the most common words in a list words = [ 'look', 'into', 'my', 'eyes', 'look', 'into', 'my', '

  • Python找出列表中出现次数最多的元素三种方式

    通过三种方式给大家介绍,具体详情如下所示: 方式一: 原理:创建一个新的空字典,用循环的方式来获取列表中的每一个元素,判断获取的元素是否存在字典中的key,如果不存在的话,将元素作为key,值为列表中元素的count # 字典方法 words = [ 'my', 'skills', 'are', 'poor', 'I', 'am', 'poor', 'I', 'need', 'skills', 'more', 'my', 'ability', 'are', 'so', 'poor' ] dict

  • js如何找出两个数组中不同的元素

    目录 js找出两个数组中不同的元素 js找出两个数组中不同元素和相同元素的几种方法 找出不同元素 找出相同的元素 总结 js找出两个数组中不同的元素 function getNewArr(a,b){ const arr = [...a,...b]; const newArr = arr.filter(item => { return !(a.includes(item) && b.includes(item)); }); return newArr; } console.log(ge

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

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

  • 浅谈pandas筛选出表中满足另一个表所有条件的数据方法

    今天记录一下pandas筛选出一个表中满足另一个表中所有条件的数据.例如: list1 结构:名字,ID,颜色,数量,类型. list1 = [['a',1,255,100,'03'],['a',2,481,50,'06'],['a',47,255,500,'03'],['b',3,1,50,'11']] list2结构:名字,类型,颜色. list2 = [['a','03',255],['a','06',481]] 如何在list1中找出所有与list2中匹配的元素?要得到下面的结果:lis

  • 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

随机推荐