找到链表的倒数第n个结点

[!Tip]

本节源代码见Github链接🔗


问题描述

找到链表的倒数第n个结点


核心思路

通过双指针来解决。主要包含以下4步:

  1. 创建两个指向头结点的指针;
  2. 先将其中一个指针移动到第n个结点,另一个指针不动;
  3. 同时移动两个指针,直到走在前面的指针移动到表尾结点,走在后面的指针则是指向倒数第n个结点;
  4. 注意判断异常边界情况。 找到倒数第n个结点.png

实现代码

【👉🏻>>点击展开查看代码】
        
/**  
 * 找到链表倒数第n个结点  
 *  
 * @param headNode  
 * @param n  
 * @return org.example.linkedlist.normal.NormalListNode  
 * @author: Max Solider  
 * @date: 2022/10/9 10:45  
 */
 NormalListNode findNthNodeFromEnd(NormalListNode headNode, int n) {  
    if (headNode == null) {  
        return headNode;  
    }  
    if (n < 1) {  
        System.out.println("The N is invalid. The N must be greater than 0.");  
        return null;    }  
    NormalListNode p1 = headNode, p2 = headNode;  
    int count = 1;  
    while (count != n) {  
        p2 = p2.getNext();  
        if (p2 == null) {  
            System.out.println("The N is invalid. The N must be less than " + (count + 1));  
            return null;        }  
        count++;  
    }  
    while (p2.getNext() != null) {  
        p1 = p1.getNext();  
        p2 = p2.getNext();  
    }  
    System.out.println("倒数第" + n + "个结点的值是:" + p1.getData());  
    return p1;  
}
        
    

时间复杂度

时间复杂度为O(n),用于扫描长度为n的链表。


空间复杂度

空间复杂度为O(1),用于存储临时变量。


© MaxSolider all right reserved,powered by Gitbook文件修订时间: 2022-10-12 23:28:30

results matching ""

    No results matching ""