文章目录

• 前言
• 一、Leetcode--203移除链表元素
• • 1.1题目描述
  • 1.2思路讲解
  • 1.3代码实现
  • • 1.3.1迭代法
    • 1.3.2虚拟头结点法
    • 1.3.3递归写法
• 二、Leetcode--83删除排序链表中的重复元素
• • 1.题目描述
  • 2.思路讲解
  • 3.代码实现
  • • 3.1迭代
    • 3.2递归写法
• 三、 Leetcode--82删除链表的重复元素||
• • 1.题目描述
  • 2.思路讲解
  • 3.代码实现
  • • 3.1迭代
    • 3.2递归写法

前言

本篇博客我们一起来看看单链表的笔试题

一、Leetcode–203移除链表元素

1.1题目描述

1.2思路讲解

我们仔细看一下题目，题目需要删除所有值为val的节点，并返回新的头结点，也就是删除后链表的头结点，此时看到这道题跟链表的删除中的删除所有值为val的节点一样，重点讲一下，递归写法的思路，写递归的时候，我们一定要重视函数的语义

这个函数的要做的事就是：传入一个链表的头结点和待删除的值val，返回删除后的链表头结点，头结点之后的值为val的删除交给子函数

1.3代码实现

1.3.1迭代法

/** * 删除链表中所有值为val的结点 */public class Num203_RemoveLinkedListElement {    public ListNode removeElements(ListNode head, int val) { while(head != null && head.val == val){     ListNode x = head;     head = head.next;     x.next = null; } if (head == null){     return null; }else{     ListNode prev = head;     while (prev.next != null){  if (prev.next.val == val){      ListNode node  = prev.next;      prev.next = node.next;  }else{      prev = prev.next;  }     } } return head;    }

1.3.2虚拟头结点法

/**     * 虚拟头结点法     * @param head     * @param val     * @return     */    public ListNode removeElements(ListNode head, int val) { ListNode dummyHead = new ListNode(); //记得连接当前链表 dummyHead.next = head; ListNode prev = dummyHead; while(prev.next != null){     if (prev.next.val == val){  prev.next = prev.next.next;     }else{  prev = prev.next;     } } return dummyHead.next;    }

1.3.3递归写法

/**     * 传入一个链表的头结点head和待删除结点值val，就能删除删除所有值为val的结点，并返回删除后的头结点     * @param head     * @param val     * @return     */    public ListNode removeElements(ListNode head, int val) {    if (head == null){ return null;    }    //从第二结点开始的删除交给子函数    head.next = removeElements(head.next,val);    //只需要head的情况 if (head.val == val){     return head.next; } return head;    }

二、Leetcode–83删除排序链表中的重复元素

1.题目描述

2.思路讲解

读题之后，我们发现本题和链表的普通删除是不一样的，普通的链表删除，是给定我们一个值或者给定一个索引，然后再删除，但是本题没有给，而我们不知道哪些节点是重复的，这就需要我们自己
1.先找找到链表中的重复节点
2.然后再根据题目要求进行操作
3prev —> 指向待删除节点的前驱，而此时一个引用是无法找到重复元素的，那我们就要引入第二个引用cur，cur = prev.next;
4.如果prev.val == cur.val，说明这两个节点重复
5.让prev = head; cur = prev.next;当出现重复元素时，prev一定是第一个重复的元素，此时让cur引用向后移动，知道碰到第一个和prev不相等节点，我们让prev.next = cur，此时我们就删除了重复节点，而且还保留了一个prev的值，与题目相吻合

3.代码实现

3.1迭代

public class Num83_DeleteDuplicates {    public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null){     return head; } ListNode prev = head; ListNode cur = prev.next; while(cur != null){     if (prev.val != cur.val){  prev = prev.next;     }else{  prev.next = cur.next;     }     cur = cur.next; } return head;    }}

3.2递归写法

public class Num83_DeleteDuplicates {   /**     * 递归     * 传入一个链表，就能删除其中值重复的结点，重复结点保留一次，并返回删除后的头结点     *     * @param head     * @return     */    public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) {     return head; } head.next = deleteDuplicates(head.next); if (head.val == head.next.val) {     return head.next; } return head;    }}}

三、 Leetcode–82删除链表的重复元素||

1.题目描述

2.思路讲解

读完题，我们发现这道题和83号题非常相似，但是区别是
83号题是删除重复节点，并保留一个重复的节点
本题是删除所有的重复节点，重复节点一个不留
1.如果使用82题的思路，那么第一个重复节点删不掉，单链表的删除都是通过前驱节点删除 — > 前驱节点删不掉，所以prev不能指向待删除的节点
2.此时prev不能指向重复节点，要判断重复节点就得再引入两个个引用，三引用
3.cur.val == nxet.val —> 判断重复元素

1.此时我们定义一个虚拟头结点，因为虚拟头结点一定不是待删除的元素，让prev从dummyHead开始走，让cur = prev.next; next = cur.next;
2.当发现cur.val != next,val,三指针同时后移
3.当cur.val == next.val ,就让next一直向后移动，直到碰到第一个不重复的节点
当next走到第一个不重复的节点，那么prev到next之间的所有结点都是待删除结点
4.prev — > 指向第一个重复结点的前驱
next — > 指向最后一个重复结点的后继
prev 到 next之间的所有节点都是待删除的节点

3.代码实现

3.1迭代

public class Num82_DeleteDuplicates {    public ListNode deleteDuplicates(ListNode head) { ListNode dummyHead = new ListNode(); dummyHead.next = head; ListNode prev = dummyHead; ListNode cur = prev.next;      while (cur != null){   ListNode next = cur.next;   if (next == null){//当前链表只有一个结点//next走到空，所有节点删除完毕break;   }else{//此时链表至少右两个以上的结点if (cur.val != next.val){    //三指针后移    prev = prev.next;    cur = cur.next;}else{    //此时碰到重复元素，让next一直后移，直到碰到第一个不重复的结点    while(next != null && cur.val == next.val){ next = next.next;    }    //说明碰到第一个不重复的结点    prev.next = next;    cur = next;}   }      }      return dummyHead.next;    }}

3.2递归写法

public class Num82_DeleteDuplicates {   /**     * 传入一个排序链表，就能删除链表中所有的重复结点，返回删除后的链表的头结点     *     * @param head     * @return     */    public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) {     return head; } if (head.val != head.next.val) {     head.next = deleteDuplicates(head.next);     return head; } else {     ListNode nextHead = head.next;     while (nextHead != null && nextHead.val == head.val) {  nextHead = nextHead.next;     }     return deleteDuplicates(nextHead); }    }}

2022深度学习开发者峰会 5月20日13:00让我们相聚云端，共襄盛会！麦克风网