链表倒数第n个节点

题意

找到单链表倒数第 n 个节点,保证链表中节点的最少数量为 n 。

样例

给出链表 3->2->1->5->nulln = 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 次,效率很低。

改进思路:

  1. 设 2 个指针 p1, p2
  2. 先让指针 p2 指向顺数第 n 个元素,p1 指向原链表的头指针。
  3. 然后 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;
    }
}

原题地址

LintCode:链表倒数第n个节点

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏赵俊的Java专栏

旋转链表

1784
来自专栏有趣的Python

算法与数据结构(三)高级排序算法:O(nlogn)的算法:归并排序&快速排序优化对比

O(nlogn)的算法 ? o(nlogn)比O(n^2)快多少 优化改进的算法要比笨的算法快太多。 归并排序:Merge Sort ? 把数组分成左右两半 ?...

5945
来自专栏编程

Python内置函数int高级用法

int()函数常用来把其他类型转换为整数,例如: >>>int(3.2) 3 >>>int(1/3) 其实,int是Python内置类型之一,之所以能够当作函数...

2589
来自专栏Python小屋

Python内置函数int()高级用法

int()函数常用来把其他类型转换为整数,例如: >>> int(3.2) 3 >>> int(1/3) 0 其实,int是Python内置类型之一,之所以能...

3057
来自专栏武培轩的专栏

剑指Offer-链表中倒数第k个结点

题目描述 输入一个链表,输出该链表中倒数第k个结点。 思路 为了能够只遍历一次就能找到倒数第k个节点,可以定义两个指针: 快指针从链表的头指针开始遍历向前走k-...

3449
来自专栏小二的折腾日记

剑指offer-刷题总结

分析:由于每一行都有递增的特性,我们可以采用类似二分搜索的方法。将数组分成行列来进行搜索。

6822
来自专栏IT可乐

深入理解计算机系统(2.6)------整数的运算

  前面两篇博客我们详细讲解了计算机中整数的表示,包括有符号和无符号(补码编码)的详细介绍。那么这篇博客我们将对它们的运算有个详细的了解。   在讲解之前首先看...

2617
来自专栏desperate633

LeetCode 19. Remove Nth Node From End of List题目分析代码

样例 给出链表1->2->3->4->5->null和 n = 2. 删除倒数第二个节点之后,这个链表将变成1->2->3->5->null.

674
来自专栏专注研发

桶排序/基数排序(Radix Sort)

基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要...

7902
来自专栏算法channel

1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。

740

扫码关注云+社区

领取腾讯云代金券