[LeetCode] Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.
Example
Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5

解题思路

定义两个指针pre和cur，如果cur的值为val，则删除该结点。需要注意的情况有两种：①需要删除头结点；②链表为空。

实现代码[C++]

//Runtime:38ms
#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL){}
};

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head != NULL && head->val == val)
        {
            head = head->next;
        }

        if (head == NULL)
        {
            return NULL;
        }
        ListNode *pre = head;
        ListNode *cur = head->next;
        while(cur != NULL)
        {
            if (cur->val == val)
            {
                pre->next = pre->next->next;
            }
            else
            {
                pre = pre->next;
            }
            cur = cur->next;
        }

        return head;
    }
};

void print(ListNode *head)
{
    while (head != NULL)
    {
        cout<<head->val;
        head = head->next;
    }
    cout<<endl;
}

int main()
{
    Solution s;
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(1);
    ListNode *node4 = new ListNode(2);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    print(node1);
    node1 = s.removeElements(node1, 2);
    print(node1);
}

实现代码[Python]

# Rumtime:181ms
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # @param {ListNode} head
    # @param {integer} val
    # @return {ListNode}
    def removeElements(self, head, val):
        while head != None and head.val == val:
            head = head.next
        if head == None:
            return None
        pre = head
        cur = head.next
        while cur != None:
            if cur.val == val:
                pre.next = pre.next.next
            else:
                pre = pre.next
            cur = cur.next

        return head

def printList(head):
    # @param {ListNode} head
    while head != None:
        print(head.val, end = ' ')
        head = head.next
    print() # print '\n'

node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(1)
node4 = ListNode(2)
node1.next = node2
node2.next = node3
node3.next = node4

printList(node1) # print the origin list
s = Solution();
node1 = s.removeElements(node1, 1)
printList(node1) # print the result list