删除链表的倒数第 N 个结点(力扣19)

el/2024/3/2 12:41:05

题目描述

题目链接:力扣icon-default.png?t=M276https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

解法要点

        这题很简单,要删除倒数第 n 个结点,就是要找到倒数第 n+1 个节点,然后将其后继指针指向第 n-1 个节点就行了。

        要找第 n+1 个结点也很容易,前后两个指针,第一个指针先走 n  步,第二个指针再出发,两个节点同时后移,当先出发的指针的后继结点为 null 时,说明它已经到尾部了,而后出发的指针正好在倒数第 n+1 个结点上。

        这里有个小技巧,需要在头部设置一个虚拟头结点,防止正好删除到头结点,把头结点丢掉的情况。

        

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyNode = new ListNode();dummyNode.next = head;ListNode first = dummyNode;ListNode last = dummyNode;// 题目中承诺 1<=n<=sz,所以,这里不用考虑 first 为空的情况for(int i = 0; i <n; i++){first = first.next;}// 直到先出发的结点到达尾部,两个指针才停下// 这时后出发的指针正好指向倒数第 n+1 个结点while(first.next != null){first = first.next;last = last.next;}// 如果 n 正好等于链表长度也没关系,这时候 last 指针正好还在 dummyNode 上last.next = last.next.next;return dummyNode.next;}
}

        除了 dummyNode 的小技巧,别的好像也没什么可说的了~

现在,关于删除链表的倒数第 N 个结点这道题,你已经知道得和我一样多了~

本专栏定期更新力扣算法讲解,希望以最容易记忆的方式帮你搞定面试算法题。


http://www.ngui.cc/el/4465892.html

相关文章

计量地理-聚类

按照计量地理思想&#xff0c;对距离矩阵进行聚类&#xff0c;数据如 60.0 0.375 0.483 1.749 1.516 1.9720.375 0.0 0.776 1.596 1.336 1.7430.483 0.776 0.0 1.926 1.662 2.1541.749 1.596 1.926 0.0 0.501 0.6931.516 1.336 1.662 0.501 0.0 0.589 1.972 1.743 2.154 0.69…

C++二维数组动态分配内存

演示了结构体与普通二维指针的动态分配 #include "stdafx.h"struct POINT{double x,y; };int _tmain(int argc, _TCHAR* argv[]) {int **pData;POINT ** pPoint;int iCol 5;//列数int iRow 5;//行数pData new int*[iRow];pPoint new POINT*[iRow];for(int i 0;…

计量地理-最短路径

求解最短路径&#xff0c;输入如下 7 70 9 7 2 -1 -1 -1-1 0 -1 -1 5 -1 -1-1 5 0 2 -1 -1 -1-1 -1 4 0 -1 3 -1-1 -1 -1 -1 0 -1 6-1 3 -1 -1 11 0 9 -1 -1 -1 -1 -1 -1 0 第一行存储行列数 // ShortestRoute.cpp : Defines the entry point for the con…

计量地理-PrincipalCA主成分析

输入如下&#xff1a; 9 1 -0.8140 -0.2168 0.3355 -0.186 0.5417 0.4237 0.0378 -0.6547-0.8140 1 0.4602 -0.6613 -0.0874 -0.7306 -0.3136 -0.0634 0.8749-0.2168 0.4602 1 0.6603 -0.2394 -0.5314 -0.2072 0.0269 0.68530.3355 -0.6613 -0.6603 1 0.3829 0.6197 0.188…

计量地理-最优点的位置

输入如下&#xff1a;每一行是居民点位置和人口数 5 5 2 10 10 2.5 5 35 2 10 27.5 2.5 15 5 2 15 15 3 15 40 2 17.5 25 3.5 20 15 4 25 30 4 25 45 2 30 10 4 35 20 5 40 5 3 42.5 25 6 45 35 5 52.5 42.5 5.5 55 35 4.5 55 5 4 57.5 10…

C#-交互式绘图

结果如图所示&#xff1a; using System;using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Drawing.Drawing2D; using System.Linq; using System.Text; using System.Windows.Forms;namespace 交互式绘…

测绘-编写数字高程模型(DEM)内插程序

一、 实习目的 掌握移动曲面法数字高程模型内插原理及其内插子程序的设计方法&#xff0c;了解其它逐点高程内插方法的基本原理。 二、 实习内容 根据提供的10个数据点的坐标&#xff08;Xn,Yn,Zn&#xff09;和待求点的平面坐标&#xff08;Xp,Yp&#xff09;&#xff0…

C-链表

上图为效果图 #include <stdio.h>#include <stdlib.h> #include <malloc.h> typedef struct Node{ int data;struct Node *next;} SLIST;void inlist(SLIST *l,int a){SLIST *p,*q;int i;p(SLIST *)malloc(sizeof(SLIST));l->nextp;for(ia;i&…

获取MFC主框架

在MainFrm里面定义的是主框架的东西&#xff0c;也就是一启动就会运行的&#xff0c;所以在后面要加东西的话得获得一开始定义的框架 CMainFrame* pFrame (CMainFrame*)AfxGetApp()->m_pMainWnd; pFrame->m_wndFileView.FillFileView(); MFC一个程序只会有一个从头到尾的…

C++ listCtrl点击列头自动排序

一个函数; void CDialogTableSum::OnColumnClick(NMHDR* pNMHDR, LRESULT* pResult) {NM_LISTVIEW* pNMListView (NM_LISTVIEW*)pNMHDR;int selectcol pNMListView->iSubItem;//获得当前所选列int listcount;//总行数listcount m_listCtrl->GetItemCount();CString t…