找出链表倒数第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; }
相关推荐
-
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
-
C++中单链表的建立与基本操作
准备数据 准备在链表操作中需要用到的变量及数据结构 示例代码如下: 复制代码 代码如下: struct Data //数据结点类型 { string key; //关键字 string name; int age;};struct CLType //定义链表结构 { Data nodeData; Data *nextNode;}; 定义了链表数据元素的类型Data以及链表的数据结构CLType.结点的具体数据保存在一个结构Data中,而指针nextNode用来指向下一个结点. 我们可以
-
Linux内核链表实现过程
关于双链表实现,一般教科书上定义一个双向链表节点的方法如下: 复制代码 代码如下: struct list_node{stuct list_node *pre;stuct list_node *next;ElemType data; } 即一个链表节点包含:一个指向前向节点的指针.一个指向后续节点的指针,以及数据域共三部分.但查看linux内核代码中的list实现时,会发现其与教科书上的方法有很大的差别.来看看linux是如何实现双链表.双链表节点定义 复制代码 代码如下: struct lis
-
找出链表倒数第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个节点)
[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
随机推荐
- IOS开发实现录音功能
- asp.net下遍历页面中所有的指定控件的代码
- Linux环境下python2.7.6升级python3.5.2
- 使用winrar打包air程序为exe(包含air运行环境)
- 关于事件mouseover ,mouseout ,mouseenter,mouseleave的区别
- js从10种颜色中随机取色实现每次取出不同的颜色
- php实现的太平洋时间和北京时间互转的自定义函数分享
- WordPress中限制非管理员用户在文章后只能评论一次
- php批量缩放图片的代码[ini参数控制]
- Python编程实现双击更新所有已安装python模块的方法
- Android编程基于自定义View实现绚丽的圆形进度条功能示例
- jquery关于图形报表的运用实现代码
- Android实现微信摇骰子游戏
- 男人要处女做老婆是有科学根据的解释
- 使用mysql_udf与curl库完成http_post通信模块示例
- Java读取Properties文件几种方法总结
- JQuery跳出each循环的方法
- 浅谈C++左值引用和右值引用
- C#实现Json转DataTable并导出Excel的方法示例
- 使用koa2创建web项目的方法步骤