个人主页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.nextprev指向新的节点。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
