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

解题思路

如果删除的节点为 head，那么我们需要对返回值做特殊处理，为了避免这样的特殊处理，我们使用一个虚拟头节点 dummyHead，并让 dummyHead 的 next 指针指向 head。这样一来，无论删除的节点是否为头节点，我们都返回 dummyHead.next 即可。

算法流程：

维护两个指针：pre，cur

初始化：

  • pre = dummyHead
  • cur = head

当 cur.val != val 时，pre,cur 指针同时向后移动

当遍历到 cur.val == val 时，让 pre.next 指向 cur.next，并让 cur.next 指向空值，跳出循环，返回 dummyHead.next

代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public ListNode deleteNode(ListNode head, int val) {
  11.         ListNode dummyHead = new ListNode(-1);
  12.         dummyHead.next = head;
  13.         ListNode cur = head;
  14.         ListNode pre = dummyHead;
  15.         while(cur != null){
  16.             if(cur.val == val){
  17.                 pre.next = cur.next;
  18.                 cur.next = null;
  19.                 break;
  20.             }else {
  21.                 cur = cur.next;
  22.                 pre = pre.next;
  23.             }
  24.         }
  25.         return dummyHead.next;
  26.     }
  27. }

复杂度分析

  • 时间复杂度：O(N)

N 为链表长度，最差的情况为删除的节点为链表最后一个节点，时间复杂度为 O(N)

  • 空间复杂度：O(1)

dummyHead,cur,pre 占用常数大小的额外空间