在之前刷力扣的过程中，我每刷道题都是先看题解然后再去边写边看，很多内容根本没消化，在进度上欺骗自己，感觉之前刷的都忘了，能力没有什么提升，现在还是一道都不会做。所以这次报了卡哥的算法训练营，希望能够按计划地有效刷题。本次刷题，我用的是 Java 语言解题，有余力的话也可能会加上 C++ 的题解。以下是算法训练营第三天的刷题记录和思考笔记。
一、链表理论基础 链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向 null（空指针）。链表的入口节点称为链表的头结点也就是 head。
链表节点的定义：
1 2 3 4 5 6 7 8 9 10 11 12 13 public class ListNode { int val; ListNode next; public ListNode () { } public ListNode (int val) { this .val = val; } public ListNode (int val, ListNode next) { this .val = val; this .next = next; } }
链表在内存中的存储方式是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
链表和数组的区别：数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
除此以外，还有双链表、循环链表和静态链表，以及它们的 C/C++ 的定义方式可以参考这篇文章 。
双链表结点的定义：
1 2 3 4 5 6 7 8 class ListNode { int val; ListNode next,prev; ListNode() {}; ListNode(int val){ this .val = val; } }
链表一定要分清节点和指针的概念。 new ListNode() 是真实存在的一个节点，head = new ListNode() 相当于 head 指针指向了一个真实的节点，node = head 相当于 node 和 head 同时指向了这个真实的节点。
二、203 移除链表元素 题目 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。
1 2 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
解题思路 第一种操作：直接使用原来的链表来进行移除。移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点（head = head -> next）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public ListNode removeElements (ListNode head, int val) { while (head != null && head.val == val){ head = head.next; } ListNode current = head; while (current != null ){ while (current.next != null && current.next.val == val){ current.next = current.next.next; } current = current.next; } return head; } }
其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。最后呢在 return 头结点的时候，return dummyNode->next;， 这才是新的头结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public ListNode removeElements (ListNode head, int val) { if (head == null ){ return head; } ListNode dummy = new ListNode (-1 , head); ListNode previous = dummy; ListNode current = head; while (current != null ){ if (current.val == val){ previous.next = current.next; }else { previous = current; } current = current.next; } return dummy.next; } }
三、707 设计链表 题目 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
1 2 3 4 5 6 7 MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3 linkedList.get(1); //返回2 linkedList.deleteAtIndex(1); //现在链表是1-> 3 linkedList.get(1); //返回3
解题思路 这道题目设计链表的五个接口，覆盖了链表的常见操作：
获取链表第 index 个节点的数值，注意 index 是从 0 开始的，第 0 个节点就是头结点。
在链表的最前面插入一个节点，等价于在第 0 个元素前添加。
在链表的最后面插入一个节点，等价于在 (末尾+1) 个元素前添加。
在链表第 index 个节点前面插入一个节点，例如 index 为 0，那么新插入的节点为链表的新头节点。如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点。如果 index 大于链表的长度，则返回空。
删除链表的第 index 个节点
可以设置一个虚拟头结点再进行操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 class MyLinkedList { int size; ListNode head; public MyLinkedList () { size = 0 ; head = new ListNode (0 ); } public int get (int index) { if (index < 0 || index >= size) { return -1 ; } ListNode currentNode = head; for (int i = 0 ; i <= index; i++) { currentNode = currentNode.next; } return currentNode.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 > size) { return ; } if (index < 0 ) { index = 0 ; } size++; ListNode pred = head; for (int i = 0 ; i < index; i++) { pred = pred.next; } ListNode toAdd = new ListNode (val); toAdd.next = pred.next; pred.next = toAdd; } public void deleteAtIndex (int index) { if (index < 0 || index >= size) { return ; } size--; if (index == 0 ) { head = head.next; return ; } ListNode pred = head; for (int i = 0 ; i < index; i++) { pred = pred.next; } pred.next = pred.next.next; } }
补充（双链表） 如果本题目是双链表进行操作：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 class MyLinkedList { int size; ListNode head,tail; public MyLinkedList () { this .size = 0 ; this .head = new ListNode (0 ); this .tail = new ListNode (0 ); head.next=tail; tail.prev=head; } public int get (int index) { if (index<0 || index>=size){ return -1 ; } ListNode cur = this .head; if (index >= size / 2 ){ cur = tail; for (int i=0 ; i< size-index; i++){ cur = cur.prev; } }else { 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); } public void addAtIndex (int index, int val) { if (index>size){ return ; } if (index<0 ){ index = 0 ; } size++; ListNode pre = this .head; for (int i=0 ; i<index; i++){ pre = pre.next; } ListNode newNode = new ListNode (val); newNode.next = pre.next; pre.next.prev = newNode; newNode.prev = pre; pre.next = newNode; } public void deleteAtIndex (int index) { if (index<0 || index>=size){ return ; } size--; ListNode pre = this .head; for (int i=0 ; i<index; i++){ pre = pre.next; } pre.next.next.prev = pre; pre.next = pre.next.next; } }
四、206 反转链表 题目 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
1 2 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
解题思路 如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。其实只需要改变链表的 next 指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。
首先定义一个 cur 指针，指向头结点，再定义一个 pre 指针，初始化为 null。然后就开始反转，首先要把 cur->next 节点用 tmp 指针保存一下，也就是保存一下这个节点。接下来要改变 cur->next 的指向，将 cur->next 指向 pre ，即反转第一个节点。接下来循环遍历继续移动 pre 和 cur 指针。最后，cur 指针已经指向了 null，循环结束，链表也反转完毕了。 此时，pre 指针就指向了新的头结点，我们 return pre 指针就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public ListNode reverseList (ListNode head) { ListNode prev = null ; ListNode curr = head; ListNode temp = null ; while (curr != null ) { temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; } }
也可以用递归法解此题，递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当 cur 为空的时候循环结束，不断将 cur 指向 pre 的过程。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public ListNode reverseList (ListNode head) { return reverse(null , head); } private ListNode reverse (ListNode prev, ListNode cur) { if (cur == null ) { return prev; } ListNode temp = null ; temp = cur.next; cur.next = prev; return reverse(cur, temp); } } class Solution { ListNode reverseList (ListNode head) { if (head == null ) return null ; if (head.next == null ) return head; ListNode last = reverseList(head.next); head.next.next = head; head.next = null ; return last; } }
