移除链表元素-203

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

示例 2：

Input: head = [], val = 1
Output: []

示例 3：

Input: head = [7,7,7,7], val = 7
Output: []

提示：

• 列表中的节点在范围 [0, 10] 内；
• 1 ≤ Node.val ≤ 50；
• 0 ≤ k ≤ 50

思路

首先，如果前导元素是val，用一个while()循环把前导元素都删掉；

然后新建一个cur_node和一个next_node指针，用于指向当前节点和下一个节点；

最后就是模拟删除链表的操作了，考验读者代码实现的能力。

代码

Cpp：

// 24ms, 14.8MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    ListNode* tmp_node;
public:
    ListNode* removeElements(ListNode* head, int val) {
        if( head == nullptr )   return nullptr;
        // Skip leading target
        while( head != nullptr && head->val == val ) {
            tmp_node = head;
            head = head->next;
            delete tmp_node;
        }
        if( head == nullptr )   return nullptr;
        if( head->next == nullptr )   return head;
        ListNode* cur_node = head;
        ListNode* next_node = head->next;
        while( cur_node != nullptr && next_node != nullptr ) {
            if( next_node->val == val ) {       // delete a node
                tmp_node = next_node;
                next_node = next_node->next;
                cur_node->next = next_node;
                delete tmp_node;
            }
            else {      // move forward
                cur_node = cur_node->next;
                next_node = next_node->next;
            }
        }
        return head;
    }
};

Rust：

// 4ms, 2.6MB
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
        if let None = head {
            return None;
        }
        let mut head: Option<Box<ListNode>> = head;
        let mut cur_node = head.as_mut().unwrap();
        while let Some(i) = cur_node.next.as_mut() {
            if i.val == val {
                cur_node.next = i.next.take();
            } else {
                cur_node = cur_node.next.as_mut().unwrap();
            }
        }
        let last_1_standing = head.as_mut().unwrap();
        if last_1_standing.val == val {
            return head.unwrap().next;
        }
        head
    }
}