删除链表的节点

---

题目：

题解：

1、单指针

1.1 未设哨兵节点dummyHead

• 解题思路：值相等时，如果是第一个节点，直接让head指向他的下一个；如果不是第一个节点，l.next = l.next.next。

• 复杂度分析：

  • 时间复杂度 O(N) ： N 为链表长度，删除操作平均需循环 N/2 次，最差 N 次。
  • 空间复杂度 O(1)

• 代码：

  // 未设哨兵节点dummyHead
  class Solution {
      public ListNode deleteNode(ListNode head, int val) {
          if (head == null) {
              return head;
          }
          if (head.val == val) {
              return head.next;
          }
          ListNode l = head;
          while (l.next != null) {
              if (l.next.val == val) {
                  l.next = l.next.next;
                  break;
              }
              l = l.next;
          }
  
          return head;
      }
  }

1.2 设哨兵节点dummyHead

• 解题思路：哨兵节点指向head，让节点l指向哨兵节点，值相等时，l.next = l.next.next。

• 复杂度分析：

  • 时间复杂度 O(N) ： N 为链表长度，删除操作平均需循环 N/2 次，最差 N 次。
  • 空间复杂度 O(1)

• 代码：

  // 设哨兵节点dummyHead
  class Solution2 {
      public ListNode deleteNode(ListNode head, int val) {
          if (head == null) {
              return head;
          }
          // 设哨兵节点
          ListNode dummyHead = new ListNode(1);
          dummyHead.next = head;
  
          ListNode l = dummyHead;
          while (l.next != null) {
              if (l.next.val == val) {
                  l.next = l.next.next;
                  break;
              }
              l = l.next;
  
          }
  
          return dummyHead.next;
      }
  }

2、双指针

• 解题思路：

  1. 定位节点： 遍历链表，直到 head.val == val 时跳出，即可定位目标节点。
  2. 修改引用： 设节点 cur 的前驱节点为 pre ，后继节点为 cur.next ；则执行 pre.next = cur.next ，即可实现删除 cur 节点。

• 复杂度分析：

  • 时间复杂度 O(N) ： N 为链表长度，删除操作平均需循环 N/2 次，最差 N 次。
  • 空间复杂度 O(1)

• 代码：

  // 双指针
  class Solution3 {
      public ListNode deleteNode(ListNode head, int val) {
          if(head.val == val) return head.next;
          ListNode pre = head, cur = head.next;
          while(cur != null && cur.val != val) {
              pre = cur;
              cur = cur.next;
          }
          if(cur != null) pre.next = cur.next;
          return head;
      }
  }