leetcode-203-移除链表元素

[博客链接]

一个菜🐔的学习之路

[题目描述]

  1. 删除链表中等于给定值 val 的所有节点。 
  3.  示例: 
  5.  输入: 1->2->6->3->4->5->6, val = 6
  6. 输出: 1->2->3->4->5
  8.  Related Topics 链表

[题目链接]

leetcode题目链接

[github地址]

代码链接

[思路介绍]

思路一：单指针

  • 定义一个指针，通过next指针进行遍历右移，然后返回头节点即可
  1. public ListNode removeElements(ListNode head, int val) {
  2.             if (head == null) {
  3.                 return head;
  4.             }
  5.             ListNode dummy = new ListNode(Integer.MIN_VALUE);
  6.             dummy.next = head;
  7.             ListNode pre = dummy;
  8.             while (pre.next != null) {
  9.                 if (pre.next.val != val) {
  10.                     pre = pre.next;
  11.                 }else {
  12.                     pre.next = pre.next.next;
  13.                 }
  14.             }
  15.             return  dummy.next;
  16.         }

时间复杂度O(n)

思路一：双指针

  • 定义两个指针一个前驱指针，一个后驱指针
  • 后驱指针遍历到给定val元素后自己向后移动一个节点，前驱指针跳跃到移动后节点，完成删除任务
  • 如果未遍历到给定val同时右移
  1. public ListNode removeElements(ListNode head, int val) {
  2.             ListNode dummy = new ListNode(Integer.MIN_VALUE);
  3.             dummy.next = head;
  4.             ListNode pre = dummy;
  5.             ListNode last = dummy.next;
  6.             while (last != null){
  7.                 if (last.val == val){
  8.                     last = last.next;
  9.                     pre.next = last;
  10.                 }else{
  11.                     last = last.next;
  12.                     pre = pre.next;
  13.                 }
  14.             }
  15.             return dummy.next;
  16.         }

时间复杂度O(n)