链表倒数第n个节点
题意
找到单链表倒数第 n 个节点，保证链表中节点的最少数量为 n 。
样例
给出链表 3->2->1->5->null 和 n = 2，返回倒数第二个节点的值 1
思路1
一个简单的思路就是先将链表进行反转，然后在反转后的链表中，顺着找第 n 个元素即可。
代码实现1
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The first node of linked list.
* @param n: An integer.
* @return: Nth to last node of a singly linked list.
*/
ListNode nthToLast(ListNode head, int n) {
ListNode node = null;
while (head != null) {
ListNode temp = head.next;
head.next = node;
node = head;
head = temp;
}
for (int i = 1; i < n; i++) {
node = node.next;
}
return node;
}
}思路2
考虑一下思路1会出现的问题：当链表很长时，效率会大大降低。例如对于 100 个元素的链表，查找倒数第 100 个，那么就等于将链表遍历了 2 次，效率很低。
改进思路：
- 设 2 个指针 p1, p2
- 先让指针 p2 指向顺数第 n 个元素，p1 指向原链表的头指针。
- 然后 p1 和 p2 一起向后移动，直到 p2 指向 NULL，此时 p1 就会指向倒数第 n 个元素上。
代码实现2
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The first node of linked list.
* @param n: An integer.
* @return: Nth to last node of a singly linked list.
*/
ListNode nthToLast(ListNode head, int n) {
if (head == null || n < 1) {
return null;
}
ListNode p1 = head;
ListNode p2 = head;
for (int j = 0; j < n - 1; ++j) {
if (p2 == null) {
return null;
}
p2 = p2.next;
}
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}原题地址
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-07-192，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录