删除链表的倒数第N个结点(双指针法)

题目链接:19. 删除链表的倒数第 N 个结点

思路:本题为双指针的经典应用,如果要删除倒数第n个结点,则先让fast移动n步,然后同时移动fast和slow,直至fast指向链表的最后一个结点,此时slow->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:
    //通过快慢指针,先让快指针移动n位,然后快慢指针同时移动,直到快指针指向最后一个结点
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    	//虚拟头指针_dummyHead,将实际头结点的删除与其他结点的删除逻辑统一
        ListNode* _dummyHead = new ListNode(0, head);
        ListNode* fastNode = _dummyHead;
        ListNode* slowNode = _dummyHead;
        while(n-- && fastNode != nullptr){
            fastNode = fastNode->next;
        }
 
        while(fastNode->next != nullptr){
            fastNode = fastNode->next;
            slowNode= slowNode->next;
        }
        
        ListNode *tmp = slowNode->next;
        slowNode->next = tmp->next;
        delete tmp;
        return _dummyHead->next;
    }
};
上一篇:【学透链表-反转链表】


下一篇:刷题之合并两个有序链表