【leetcode】203. 移除链表元素

目录标题

算法汇总

以下是所有算法汇总,包括GitHub源码地址链接:力扣算法练习汇总(持续更新…)

题目

203. 移除链表元素
【leetcode】203. 移除链表元素

思路

定义一个虚拟节点

代码

1.迭代法

【leetcode】203. 移除链表元素

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**
      思路:添加一个头节点
     */
    public ListNode removeElements(ListNode head, int val) {
        // 定义一个头节点
       ListNode newHead = new ListNode(0);
        // head作为新节点的next
        newHead.next = head;
        // 定义临时节点
        ListNode temp = newHead;
        while(temp.next != null){
            if(temp.next.val == val){
                temp.next = temp.next.next;
            }else{
                temp = temp.next;
            }
        }
        // 返回新节点的next,因为新节点的第一个节点是我们虚拟出来的。
        return newHead.next;
    }
}

复杂度分析

  • 时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表一次。
  • 空间复杂度:O(1)。

2.递归

【leetcode】203. 移除链表元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}

复杂度分析

  • 时间复杂度:O(n),其中 nn 是链表的长度。递归过程中需要遍历链表一次。

  • 空间复杂度:O(n),其中 nn 是链表的长度。空间复杂度主要取决于递归调用栈,最多不会超过 nn 层。

上一篇:【LeetCode】19. 删除链表的倒数第 N 个结点


下一篇:线性表之链表