【LeetCode 19】删除链表的倒数第N个节点

【题解】

经典的一道题。
让p1指向链表的第一个元素。
让p2指向链表的第二个元素。
然后让他们俩同时往后移动。
直到p2到达链表的尾巴。
这时p1和p2之间总是隔了n-1个元素。
所以p1一定是倒数第n个元素。
记得加个虚拟的头结点方便删除操作(删掉了第一个数字的话)
$O(N)$

【代码】

/**

 * 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 * temp = new ListNode(0);temp->next = head;

        ListNode * ans = temp;

        ListNode *p1 = head;

        ListNode *p2 = head;

        for (int i = 1;i <= n-1;i++) p2 = p2->next;

        while (p2->next){

            temp = temp->next;

            p1 = p1->next;

            p2 = p2->next;

        }

        temp->next = p1->next;

        delete(p1);

        return ans->next;

    }

};

巴特西

【LeetCode 19】删除链表的倒数第N个节点

最新文章

热门文章