[leetcode题解]19.Remove Nth Node From End of List(删除倒数N个元素)

leetcode,19,Remove Nth Node From End of List,给定一个单链表,删除倒数第N个元素,要求进行一遍遍历即可。思路是利用两个指针,一个提前走N步,然后另一个指针指向开头,两个指针同时走,当前面的指针到尾部时,后面的指针正好位于要删除的元素位置。为了得到要删除位置的前一个位置,可以加入一个预头,然后,前面的指针从头开始,后面的指针从预头开始。

c++代码:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        if (head == NULL)return NULL;
        
        ListNode *pre = new ListNode(-1);
        pre->next = head;
        
        ListNode *fast = head, *slow = head;
        ListNode *p = pre;
        while(n--)
        {
            fast = fast->next;
        }
        
        while(fast != NULL)
        {
            fast = fast->next;
            slow = slow->next;
            p = p->next;
        }
        
        p->next = slow->next;
        delete(slow);
        return pre->next;
    }
};

python代码:

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        :author: 凌风技术站-iaccepted
        """
        pre = ListNode(-1)
        pre.next = head
        
        p = pre
        q = head
        while n > 0 and q is not None:
            q = q.next
            n -= 1
        while q is not None:
            p = p.next
            q = q.next
        p.next = p.next.next
        return pre.next

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]19.Remove Nth Node From End of List(删除倒数N个元素)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/108.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注