1. 题目描述

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

2. 题目分析

典型的前后指针的题。

假如要求倒数第n个元素,先让ptrFirst指针以头元素为起点前进n+1步,然后让ptrSecond以头元素为起点,即此时ptrFirst比ptrSecond往前n+1步,ptrSecond和ptrFirst一起一格一格向前走,那么当ptrFirst第一次指向NULL的时候,ptrSecond指向的就是倒数第n+1个元素,那么此时删除倒数第n个元素也轻而易举了。

但如果将最初的head头节点作为头部元素其实会有漏洞,比如链表有三个元素,我现在要删除倒数第三个节点即头节点,那么按照上面的方法,ptrFirst得相对于头节点向前移动4步,而可以知道相对于head移动4步已经越界了,ptrFirst会指向NULL的next所以当然会报错。

所以为了处理这种特殊情况,继续搬出dummyHead这个大救星,让dummyHead的next指向head,而让ptrFirst和ptrSecond从dummyHead开始往后走,这样ptrFirst还是比ptrSecond往前n+1步,但很容易证明此时对于删除头节点这种特殊情况不会产生越界。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummyHead =
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    dummyHead->next = head;
    struct ListNode* ptrFirst = dummyHead;
    struct ListNode* ptrSecond = dummyHead;

    for (int i = 0; i < n + 1; i++) {
        ptrFirst = ptrFirst->next;
    }

    while (ptrFirst) {
        ptrFirst = ptrFirst->next;
        ptrSecond = ptrSecond->next;
    }

    ptrSecond->next = ptrSecond->next->next;

    return dummyHead->next;
}

int main() {

    system("pause");
    return 0;
}
Last modification:September 8th, 2019 at 08:27 pm