专栏首页赵俊的Java专栏链表倒数第n个节点

链表倒数第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链表操作代码

    CherishTheYouth
  • 漫画:如何将一个链表“逆序”?

    (现实里的小灰在刚入行的时候,面试官也问了我这个问题,当时小灰就傻傻的问面试官是单链表还是双链表?然后就没然后了......)

    AndroidTraveler
  • 数组与链表

    数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

    Yif
  • 链表问题(二)-LeetCode 147、876、234、817、92(链表的中点,快慢指针)

    首先判断两个相邻节点的大小,如果head->val > head->next->val,则需要将head->next->val插入到从dummy节点开始遍历第一...

    算法工程师之路
  • LintCode 删除排序链表中的重复数字 II题目分析代码

    给定一个排序链表,删除所有重复的元素只留下原链表中没有重复的元素。 样例 给出 1->2->3->3->4->4->5->null,返回 1->2->5->...

    desperate633
  • 【链表问题】打卡6:三种方法带你优雅判断回文链表

    以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。

    帅地
  • 问题系列之Java中删除有序List的重复数据——提供两种方法

    Java学习网(www.javalearns.com)提拱 现在给出一个有序的List,删除其中重复的元素,要求第个元素只能出现一次,并且是经过的排序的; ...

    用户1289394

扫码关注云+社区

领取腾讯云代金券