虚拟头节点

在上一节的链表结构中,讲解链表结构的实现,不知道大家有没有注意到,我在实现单链表中使用了 虚拟头节点 , 虚拟头节点 的作用可以统一链表默认有一个头节点,而不用我们再去判断 head 头节点是否为空以及为空时的处理,可以使逻辑达到统一.

如下代码,如果我们不使用 虚拟头节点 我们就需要判断 head 是否为空,多了一层判断
,我们将head初始化时设置为 head = new Node<>(null, null) 那么head.next就是真正的头节点.这样我们可以保证逻辑的统一

  1.     public void add(E e, int index) {
  2.         if (index < 0 || index > size)
  3.             throw new IllegalArgumentException("index > 0 && index < size");
  4.         Node<E> perv = head;
  5.         for (int i = 0; i < index; i++) {
  6.             perv = perv.next;
  7.         }
  8.         perv.next = new Node<E>(e, perv.next);
  9.         size++;
  10.     }

如果你还是不懂的话,下面我通过一个例子来看一下,这个例子来自leetcode上的一个题库203,移除链表元素.

我们正常移除链表元素的写法如下:
我们需要首先判断链表头节点的元素是否等于要删除的元素以及是否存在多个重复的元素.

  1. public ListNode removeElements(ListNode head, int val) {
  2.         while (head != null && head.val == val) {//注意可能存在两个相等的元素
  3. //            ListNode delNode = head;//要删除的节点为头部节点
  4. //            head = head.next;//改变头部节点
  5. //            delNode.next = null;
  6.             head = head.next;
  7.         }
  8.         if (head == null) {//注意循环完之后 head可能为null
  9.             return null;
  10.         }
  11.         ListNode perv = head;//头节点判断完毕后，判断头节点的后面的节点
  12.         while (perv.next != null) {//循环下一个节点是否为空
  13.             if (perv.next.val == val) {//判断下一个节点的值
  14. //                ListNode delNode = perv.next;//要删除的节点
  15. //                perv.next = delNode.next;
  16. //                delNode.next = null;
  17.                 perv.next = perv.next.next;
  18.             } else {//继续循环下一个节点
  19.                 perv = perv.next;
  20.             }
  21.         }
  22.         return head;
  23.     }

下面来看一下,用虚拟头节点如何简化代码呢? 看下面代码,使用虚拟头节点就不用再去判断头节点的问题去掉了一层循环,同时我们的代码逻辑也更加清晰.

  1.  public ListNode removeElements2(ListNode head, int val) {
  2.         //通过虚拟头节点的作用 统一都有一个头节点 使逻辑达到统一
  3.         ListNode dummyHead = new ListNode(-1);
  4.         dummyHead.next = head;
  5.         ListNode perv = dummyHead;//头节点判断完毕后，判断头节点的后面的节点
  6.         while (perv.next != null) {//循环下一个节点是否为空
  7.             if (perv.next.val == val) {//判断下一个节点的值
  8.                 perv.next = perv.next.next;
  9.             } else {//继续循环下一个节点
  10.                 perv = perv.next;
  11.             }
  12.         }
  13.         return dummyHead.next;
  14.     }

递归

什么是递归呢? 递归就是将原来的问题,转换为更小的同一个问题.比如我们求sum(arr[n])的和,如下面代码,我们可以通过递归来计算arr[0]+arr[1]+……arr[n]

  1. public static int sum(int[] arr) {
  2.         return sum(arr, 0);
  3. }
  5. private static int sum(int[] arr, int l) {
  6.         if (l == arr.length) return 0;
  7.         return arr[l] + sum(arr, l + 1);//把原问题转化为更小的问题
  8. }

如何使用递归来实现链表的元素删除呢? 代码如下:不断的递归 head 如果haed.val==val 直接返回res,如果不相等则head.next = res;

  1.  public ListNode removeElements3(ListNode head, int val) {
  2.         if (head == null) return null;//递归的终止条件
  3.         ListNode res = removeElements3(head.next, val);
  4.         if (head.val == val)
  5.             return res;
  6.         else {
  7.             head.next = res;
  8.             return head;
  9.         }
  10.     }