Question

203. 移除链表元素

English Version

题目描述

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

 

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

 

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

解法

方法一

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#     self.val = val
#     self.next = next
class Solution:
  def removeElements(self, head: ListNode, val: int) -> ListNode:
    dummy = ListNode(-1, head)
    pre = dummy
    while pre.next:
      if pre.next.val != val:
        pre = pre.next
      else:
        pre.next = pre.next.next
    return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode() {}
 *   ListNode(int val) { this.val = val; }
 *   ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    while (pre.next != null) {
      if (pre.next.val != val)
        pre = pre.next;
      else
        pre.next = pre.next.next;
    }
    return dummy.next;
  }
}

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

func removeElements(head *ListNode, val int) *ListNode {
  dummy := new(ListNode)
  dummy.Next = head
  p := dummy
  for p.Next != nil {
    if p.Next.Val == val {
      p.Next = p.Next.Next
    } else {
      p = p.Next
    }
  }
  return dummy.Next
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 *   }
 * }
 */

function removeElements(head: ListNode | null, val: number): ListNode | null {
  const dummy: ListNode = new ListNode(0, head);
  let cur: ListNode = dummy;
  while (cur.next != null) {
    if (cur.next.val === val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }
  return dummy.next;
}

// 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>> {
    let mut dummy = Box::new(ListNode { val: 0, next: head });
    let mut cur = &mut dummy;
    while let Some(mut node) = cur.next.take() {
      if node.val == val {
        cur.next = node.next.take();
      } else {
        cur.next = Some(node);
        cur = cur.next.as_mut().unwrap();
      }
    }
    dummy.next.take()
  }
}

public class Solution {
  public ListNode RemoveElements(ListNode head, int val) {
    ListNode newHead = null;
    ListNode newTail = null;
    var current = head;
    while (current != null)
    {
      if (current.val != val)
      {
        if (newHead == null)
        {
          newHead = newTail = current;
        }
        else
        {
          newTail.next = current;
          newTail = current;
        }
      }
      current = current.next;
    }
    if (newTail != null) newTail.next = null;
    return newHead;
  }
}