企业官网建设流程全解析

个人主页：https://github.com/zbhgis

前言

本系列主要记录自己学习算法的过程中的感悟。

力扣203. 移除链表元素

链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

注意点

链表操作的题目，为了减少判断操作，都可以引入一个虚拟头节点，指向head。

这里的移除操作，就是相当于将cur指向cur.next.next，跳过中间的cur.next，就是上一篇的图示。

本质就是遍历各个节点，然后修改指针指向，以及题目如果需要返回链表的话，就是返回头节点。

代码

/** * 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 dummy = new ListNode(0, head); ListNode cur = dummy; while (cur.next != null) { if (cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } return dummy.next; } }

时空复杂度分析

单层循环，最多需要遍历n次，n为链表长度，因此时间复杂度为O(n)

空间复杂度为O(1)

力扣707. 设计链表-单向

链接：https://leetcode.cn/problems/design-linked-list/description/

注意点

定义链表就不多说了。以及各个方法中的边界判断也就不说了，特殊的就是在addAtIndex中是可以到size下标。

get方法，就是设置一个cur，去遍历各个节点，到所需下标处返回。

addAtIndex方法，就是通过一个前驱节点，得到想要添加处的前一个节点prev，最后新的节点指向prev.next，prev指向新的节点。

deleteAtIndex方法，也是通过前驱节点遍历，只不过最后是把prev指向prev.next.next，跳过了所需下标的节点。

代码

public class MyLinkedList { // 单链表节点定义 private class Node { int val; Node next; Node() {} Node(int val) { this.val = val; } Node(int val, Node next) { this.val = val; this.next = next; } } private Node dummy; // 虚拟头节点 private int size; // 链表长度 /** 初始化 */ public MyLinkedList() { dummy = new Node(0); size = 0; } /** 获取下标 index 的节点值 */ public int get(int index) { if (index < 0 || index >= size) { return -1; } Node cur = dummy.next; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.val; } /** 头插法 */ public void addAtHead(int val) { addAtIndex(0, val); } /** 尾插法 */ public void addAtTail(int val) { addAtIndex(size, val); } /** 在下标 index 前插入节点 */ public void addAtIndex(int index, int val) { if (index < 0 || index > size) return; Node prev = dummy; for (int i = 0; i < index; i++) { prev = prev.next; } Node newNode = new Node(val); newNode.next = prev.next; prev.next = newNode; size++; } /** 删除下标 index 的节点 */ public void deleteAtIndex(int index) { if (index < 0 || index >= size) return; Node prev = dummy; for (int i = 0; i < index; i++) { prev = prev.next; } prev.next = prev.next.next; size--; } }

时空复杂度分析

除了addAtHead和addAtTail方法是O(1)，其他时间复杂度为O(n)

局部空间复杂度为O(1)，整体因为要存储n个节点，所以整体空间复杂度为O(n)

力扣707. 设计链表-双向

链接：https://leetcode.cn/problems/design-linked-list/description/

注意点

同上。

代码

class MyLinkedList { public class Node { int val; Node prev; Node next; Node() {} Node(int val) {this.val = val;} Node(int val, Node prev, Node next) { this.val = val; this.prev = prev; this.next = next; } } private final Node dummyHead; private final Node dummyTail; private int size; public MyLinkedList() { dummyHead = new Node(0); dummyTail = new Node(0); dummyHead.next = dummyTail; dummyTail.prev = dummyHead; size = 0; } public int get(int index) { if (index < 0 || index >= size) return -1; Node cur; if (index < size / 2) { cur = dummyHead.next; for (int i = 0; i < index; i ++) cur = cur.next; } else { cur = dummyTail.prev; for (int i = size - 1; i > index; i --) cur = cur.prev; } return cur.val; } public void addAtHead(int val) { addAtIndex(0, val); } public void addAtTail(int val) { addAtIndex(size, val); } public void addAtIndex(int index, int val) { if (index < 0 || index > size) return; Node prev, next; if (index < size / 2) { prev = dummyHead; for (int i = 0; i < index; i ++) prev = prev.next; next = prev.next; } else { next = dummyTail; for (int i = size; i > index; i --) next = next.prev; prev = next.prev; } Node newNode = new Node(val, prev, next); prev.next = newNode; next.prev = newNode; size ++; } public void deleteAtIndex(int index) { if (index < 0 || index >= size) return; Node prev, next; if (index < size / 2) { prev = dummyHead; for (int i = 0; i < index; i ++) prev = prev.next; next = prev.next; } else { next = dummyTail; for (int i = size; i > index; i --) next = next.prev; prev = next.prev; } prev.next = next.next; next.next.prev = prev; size --; } } /** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */

时空复杂度分析

同上

力扣206. 反转链表

链接：https://leetcode.cn/problems/reverse-linked-list/description/

注意点

从前往后遍历节点，但是需要遍历到的节点找到指针方向。

代码

/** * 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 reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; } return pre; } }

时空复杂度分析

单层循环，最多需要遍历n次，n为链表长度，因此时间复杂度为O(n)

空间复杂度为O(1)

参考

https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html