目录标题
算法汇总
以下是所有算法汇总,包括GitHub源码地址链接:力扣算法练习汇总(持续更新…)
题目
思路
定义一个虚拟节点
。
代码
1.迭代法
/**
* 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.递归
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 层。