[leetcode题解]203.Remove Linked List Elements

leetcode第203题,remove linked list elements,题目给定一个单链表和一个值,要求将该单链表中所有val与该给定值相等的节点删除,结果返回删除后的链表,原链表中的元素相对位置不变。
例如:

Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

对于删除类的题目,思路很简单,因为有可能删除的元素是链表的第一个元素,所以通常对于此类题,我们都是先给链表加一个预头节点,这样即使删除头结点也跟删除内部节点有一致的操作,无需特殊对待。之后就是使用两个指针,一个遍历,另一个在后面记录当前节点的前一个节点,保证在删除节点的时候知道当前节点的前一个节点,这样便于操作,时间复杂度o(n),n为链表长度,空间复杂度o(1),这里同样是使用了python和c++来解决。

c++代码:

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        ListNode *pre = new ListNode(-1);
        pre->next = head;
        
        ListNode *p = head, *q = pre;
        while(p != NULL)
        {
            if (p->val == val)
            {
                q->next = p->next;
            }
            else q = q->next;
            
            p = p->next;
        }
        return pre->next;
    }
};

python代码:

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        pre = ListNode(-1)
        pre.next = head
        
        q = pre
        p = head
        while p != None:
            if p.val == val:
                q.next = p.next
            else:
                q = q.next
            p = p.next
        return pre.next

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

本文标题:[leetcode题解]203.Remove Linked List Elements

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

相关文章



发表评论

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