首页 🍒LeetCode,🐶算法

题目

1LCn36ESs4.png

思路

两次遍历法:
可以遍历两遍,第一遍求出链表长度,第二遍删掉倒数第n个。代码就不贴了。

双指针解法:
定义两个指针first, second。让first先走n + 1步,然后两个指针间距就是n。

然后让两个指针同时走当first走到最后时second->next就是要删除的节点删除即可。

需要注意的地方是如果要删除的是头结点的话,first走n + 1步就超出去了,所以要在first走到结尾时停止,如果走的步数少于n + 1就说明要删除的是头结点,然后直接返回head->next即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *first = head;
        ListNode *second = head;
        int m = 0;
        while (first->next != nullptr && m < n) {
            m++;
            first = first->next;
        }
        if (m != n) {
            return head->next;
        }
        while (first->next != nullptr) {
            second = second->next;
            first = first->next;
        }
        second->next = second->next->next;
        return head;
    }
};



文章评论