漫画:如何找到链表的倒数第n个结点?
source link: https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw%3D%3D&%3Bmid=2653214771&%3Bidx=1&%3Bsn=e1b8c056589fae0f04b8002ec485ad45
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
————— 第二天 —————
什么意思呢?我们以下面这个链表为例:
给定链表的头结点,但并不知道链表的实际长度,要求我们找到链表的倒数第n个结点。
假设n=3,那么要寻找的结点就是元素1:
如何利用队列呢?小灰的思路如下:
1.创建一个长度为n的队列,遍历原始链表,让结点逐一进入队列:
2.当队列已满时,让队尾元素出队,新结点入队:
3.当链表全部结点遍历完毕时,队尾的元素就是倒数第n个结点(因为队列长度是n):
————————————
首先,我们创建两个指针P1和P2,P1指向链表的头结点,P2指向链表的正数第n个结点(也就是例子中的第3个结点):
接下来,我们让指针P1和P2同时循环右移,每次右移一步,直到指针P2移动到链表的末尾:
此时,由于P2指向链表的尾结点,且P1和P2的距离是n-1,因此P1所指的结点就是我们要寻找的链表倒数第n个结点:
显然,这个方法从头到尾只需要对链表做一次遍历,而且仅仅使用了两个指针,算法的空间复杂度是O(1)。
public class NthFromEnd { public static Node findNthFromEnd(Node head, int n){ Node p1 = head; Node p2 = head; //把p2指针移动到正数第n个结点 for(int i=1; i<n; i++){ p2 = p2.next; if(p2 == null){ throw new IllegalArgumentException("参数n超出链表长度!"); } } //p1和p2一起右移,直到p2指向链表尾结点 while (p2.next != null){ p1 = p1.next; p2 = p2.next; } return p1; } //快速创建链表 private static Node buildLinkList(int[] array){ Node head = new Node(array[0]); Node p = head; for(int i=1; i<array.length; i++){ p.next = new Node(array[i]); p = p.next; } return head; } //链表节点 private static class Node { int data; Node next; Node(int data) { this.data = data; } } public static void main(String[] args) { int[] inputs = {5,3,7,2,4,1,9,8}; Node head = buildLinkList(inputs); Node node = findNthFromEnd(head,3); System.out.println("链表倒数第3个元素是:" + node.data); } }
—————END—————
喜欢本文的朋友,欢迎关注公众号 程序员小灰 ,收看更多精彩内容
点个[在看],是对小灰最大的支持!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK