关键字:链表、编程技巧 题目大意:对于一个给定的指针链表,删除其倒数第N个元素。

题目描述

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

解法

这个问题可以用一个非常巧妙的方法来进行解决,即设立两个指针p1和p2,一开始它们都指向队首,然后单独令p2向后跳n+1个元素,这样p1和p2之间就相隔了n个元素,此时令p1和p2同时向后不断跳,直到p2越过队尾(变为空),由于此时p1和p2之间相隔n个元素,所以p1的下一个元素就是我们要删除的元素了。

为了方便删除第一个元素,建议设立一个空的“头结点”。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 设立头结点
        ListNode *h = new ListNode(0);
        h -> next = head;
        // 初始化p1, p2
        ListNode *p1 = h, *p2 = h;
        for (int i = 0; i < n + 1; i++) p2 = p2 -> next;
        // 两个指针同时移动直到p2到达最后
        while (p2 != NULL) {
            p1 = p1 -> next;
            p2 = p2 -> next;
        }
        // 删除并返回
        p1 -> next = p1 -> next -> next;
        return h -> next;
    }
};

登录发表评论 注册

反馈意见