[剑指offer][JAVA]面试题第[18]题[删除链表的节点]

快来打我* 2023-02-16 12:20 8阅读 0赞

#### 【问题描述】\[中等\] ####

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
    
    返回删除后的链表的头节点。
    
    注意：此题对比原题有改动
    
    示例 1:
    
    输入: head = [4,5,1,9], val = 5
    输出: [4,1,9]
    解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

#### 【解答思路】 ####

###### 1. 双指针 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(N^2) 空间复杂度：O(1)**

class Solution { 
        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;
        }
    }

###### 2.单指针 ######

**时间复杂度：O(N) 空间复杂度：O(1)**

public ListNode deleteNode(ListNode head, int val) { 
            if(head.val == val) return head.next;
            ListNode cur = head;
    
            while(cur != null){ 
                if(cur.next.val == val ){ 
                    cur.next = cur.next.next;
                    break;
                }
                cur=cur.next;
            }
    
            return head;
        }

#### 【总结】 ####

###### 1.画图理解指针问题 ######

###### 2.遍历指针 ######

ListNode cur = head;
            while(cur != null)
                cur=cur.next;
            }

###### 3.链表为空作判断 链表头尾特殊判断 ######

参考链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/solution/mian-shi-ti-18-shan-chu-lian-biao-de-jie-dian-sh-2/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200610000046749.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200610000058526.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70