算法-单链表删除数字

燃着的半支烟 2020年04月12日 120次浏览

题目描述

给你一个单链表和一个数字,你要删除节点上数字等于给定数字的那些节点,然后返回删除节点后的单链表。

比如说,给定的单链表是:

1 → 2 → 4 → 1 → 8 → 1

要删除的数字是1。那么删除1后,返回的单链表是:

2 → 4 → 8

思路

  1. 先定义一个单链表
  2. 定义一个虚拟节点dummy,指向单链表的头节点
  3. 再定义一个移动指针节点p,逐步移动指针节点p,与给定的数字进行比较
  4. 如果给定的数字与节点p的数字相同,则断开此节点(即p.next = p.next.next);如果不相同,则继续移动指针p(即p = p.next)

WechatIMG2334

Java代码实现

private LinkedNode delNumInLinkedNode3(LinkedNode linkedNode, int num) {
  //定义虚拟节点,指向链表头部
  LinkedNode dummy = new LinkedNode(0);
  dummy.next = linkedNode;
  //定义移动节点p,凡是这种需要逐个比对的,一般都需要定义移动指针
  LinkedNode p = dummy;

  //逐个比对
  while (p.next != null) {
    //如果节点的数字 跟 给定的数字相同,则断开此节点
    if (p.next.value == num) {
      p.next = p.next.next;
    }
    //如果不相同,则继续移动指针
    else {
      p = p.next;
    }
  }

  return dummy.next;
}

代码地址