203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

---

把链表中等于val的所有节点都删掉。简单题，为了方便，先添加一个0号节点，然后记录prior和tail指针，当tail->val==val时，删掉tail节点，prior节点不动；否则prior和tail都往后移一个位置。直到tail为NULL。完整代码如下：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val)
    {
        ListNode* new_head = new ListNode(0);
        new_head->next = head;
        ListNode *prior = new_head, *tail = prior->next;
        while (tail != NULL) {
            if (tail->val == val) {
                prior->next = prior->next->next;
                tail = prior->next;
            }
            else {
                prior = prior->next;
                tail = prior->next;
            }
        }
        return new_head->next;
    }
};

本代码提交AC，用时29MS。

二刷。简化版本：

class Solution {
public:
	ListNode* removeElements(ListNode* head, int val) {
		ListNode *dummy = new ListNode(0);
		ListNode *tail = dummy;
		while (head != NULL) {
			if (head->val != val) {
				tail->next = head;
				tail = tail->next;
			}
			head = head->next;
		}
		tail->next = NULL;
		return dummy->next;
	}
};

本代码提交AC，用时20MS。