剑指 Offer 18. 删除链表的节点

image.png

遍历

  1. public class Solution {
  3.     public ListNode deleteNode(ListNode head, int val) {
  4.         // 如果是空链表，直接返回空
  5.         if (head == null) return null;
  6.         // 如果要删除的节点是第一个，直接返回 head.next
  7.         if (head.val == val) return head.next;
  9.         // 记录前一个节点
  10.         ListNode pre = head;
  11.         // 记录当前节点
  12.         ListNode cur = head.next;
  14.         while (true) {
  15.             // 如果当前节点是要删除的节点
  16.             if (cur.val == val) {
  17.                 // 令上一个节点的 next 指向当前节点的 next，停止循环
  18.                 pre.next = cur.next;
  19.                 break;
  20.             }
  21.             // 往前进一步
  22.             pre = pre.next;
  23.             cur = cur.next;
  24.         }
  25.         return head;
  26.     }
  27. }

遍历，增加伪头节点

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：37.5 MB, 在所有 Java 提交中击败了93.76%的用户

  1. class Solution {
  2.     public ListNode deleteNode(ListNode head, int val) {
  3.         // 使用伪头节点
  4.         ListNode temp = new ListNode(0);
  5.         temp.next = head;
  7.         // 记录前一个节点
  8.         ListNode pre = temp;
  9.         // 记录当前节点
  10.         ListNode cur = temp.next;
  11.         while (true) {
  12.             // 如果当前节点是要删除的节点
  13.             if (cur.val == val) {
  14.                 // 令上一个节点的 next 指向当前节点的 next，停止循环
  15.                 pre.next = cur.next;
  16.                 break;
  17.             }
  18.             // 往前进一步
  19.             pre = pre.next;
  20.             cur = cur.next;
  21.         }
  22.         return temp.next;
  23.     }
  24. }

递归

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：37.8 MB, 在所有 Java 提交中击败了66.79%的用户

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) return null;

        if (head.val == val) return head.next;
        else head.next = deleteNode(head.next, val);

        return head;
    }
}