链表
概念
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。
分类
单链表
链表通过指针将一组零散的内存块串联在一起。其中，内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。
双链表
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点。
循环链表
循环链表的尾结点指针是指向链表的头结点。
特点
- 链表查找、插入和删除操作只需要改变 next 指针的指向，O(1)的时间复杂度。
- 链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。
- 内存空间占用不要求连续
作业题
203. 移除链表元素
- 直接编辑法
package jjn.carl.linkedlist; import commons.LinkedListHelper; import commons.ListNode; import java.lang.management.ThreadInfo; import java.util.List; /** * @author Jiang Jining * @since 2023-06-30 21:51 */ public class LeetCode203_WithoutDummy { public ListNode removeElements(ListNode head, int val) { if (head == null) { return null; } // 从头开始,去除全部目标等于val的节点 while (head != null) { if (head.val == val) { head = head.next; } else { break; } } ListNode start = head; while (start != null && start.next != null) { if (start.next.val == val) { start.next = start.next.next; } else { start = start.next; } } return head; } public static void main(String[] args) { ListNode listNode = LinkedListHelper.buildLinkedList(List.of(6, 6, 6, 6, 6)); ListNode node = new LeetCode203_WithoutDummy().removeElements(listNode, 6); while (node != null) { System.out.println("node.val = " + node.val); node = node.next; } } }
- 头结点法
package jjn.carl.linkedlist; import commons.LinkedListHelper; import commons.ListNode; import java.util.List; /** * @author Jiang Jining * @since 2023-06-30 21:51 */ public class LeetCode203 { public ListNode removeElements(ListNode head, int val) { // 添加虚拟头结点，让遍历条件统一 ListNode dummy = new ListNode(-1); dummy.next = head; ListNode start = dummy; while (start.next != null) { if (start.next.val == val) { start.next = start.next.next; } else { start = start.next; } } return dummy.next; } public static void main(String[] args) { ListNode listNode = LinkedListHelper.buildLinkedList(List.of(6,2,3,4,5,6,7)); ListNode node = new LeetCode203().removeElements(listNode, 6); while (node != null) { System.out.println("node.val = " + node.val); node = node.next; } } }
707. 设计链表
这一题边界条件也太难搞了。
class MyLinkedList { class Node { int val; Node next; public Node(int val) { this.val = val; } } private final Node dummy; private int size; public MyLinkedList() { dummy = new Node(0); size = 0; } public int get(int index) { Node start = dummy; if (index < 0 || index > size - 1) { return -1; } while (index >= 0) { start = start.next; index--; } return start.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 start = dummy; while (index > 0) { start = start.next; index--; } Node next = new Node(val); next.next = start.next; start.next = next; size++; } public void deleteAtIndex(int index) { if (index >= size) { return; } Node start = dummy; while (index > 0) { start = start.next; index--; } start.next = start.next.next; 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. 反转链表
遍历法
public ListNode reverseList(ListNode head) { ListNode current = head, previous = null; while (current != null) { // 必须使用temp存储一下current的下一个节点，防止找不到 ListNode temp = current.next; // 当前节点指向掉头 current.next = previous; // 移动前一个节点 previous = current; current = temp; } return previous; }
递归法
public ListNode reverseList(ListNode head) { return reverse(head, null); } private ListNode reverse(ListNode current, ListNode pre) { if (current == null) { return pre; } ListNode temp = current.next; current.next = pre; return reverse(temp, current); }
