1.数据结构之链表
链表是最基本的动态数据结构，是真正的动态结构，不需要处理固定容量，但与此同时带来的是随机访问能力的丧失，其原因是底层内存分配不连续。
小tip：虚拟头节点dummy的作用在于，让对链表头节点的操作和链表中其他节点的操作相同，不需要对头节点单独处理。
2.链表相关题目
2.1从尾到头打印链表
边界情况：①功能测试：含一个或多个节点的链表；②边界情况：空链表
思路分析：其本质是后进先出，是栈的结构，而栈的结构归根结底是递归操作。
可采取方法：入栈出栈、递归、头插法重新生成链表再遍历，如何选择方法需根据情况进行，若不能修改链表结构则采用栈或递归的方式，若无要求则可采用头插法。
而采用递归的方式可能在链表长度过大时是的栈溢出，故而采用栈的方式更好。
①头插法（O(N)的时间复杂度）
1 import java.util.ArrayList;
2 public class Solution {
3 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
4 ArrayList<Integer> result = new ArrayList<>();
5 if (listNode == null) return result;
6 ListNode dummy = new ListNode(0);
7 ListNode cur = listNode;
8 while (cur != null) {
9 ListNode tmp = cur;
10 cur = cur.next;
11 tmp.next = dummy.next;
12 dummy.next = tmp;
13
14 }
15 cur = dummy.next;
16 while (cur != null) {
17 result.add(cur.val);
18 cur = cur.next;
19 }
20 return result;
21 }
22 }
②栈的方式（O(N)的时间复杂度）
1 import java.util.ArrayList;
2 import java.util.*;
3 public class Solution {
4 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
5 ArrayList<Integer> result = new ArrayList<>();
6 Stack<Integer> stack = new Stack<>();
7 if (listNode == null) return result;
8 ListNode dummy = new ListNode(0);
9 ListNode cur = listNode;
10 while (cur != null) {
11 stack.push(cur.val);
12 cur = cur.next;
13 }
14 while (!stack.isEmpty()) {
15 result.add(stack.pop());
16 }
17 return result;
18 }
19 }
③递归的方式（O(N)的时间复杂度）
1 import java.util.ArrayList;
2 public class Solution {
3 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
4 ArrayList<Integer> result = new ArrayList<>();
5 printList(listNode, result);
6 return result;
7 }
8 private void printList(ListNode pHead, ArrayList<Integer> result) {
9 if (pHead != null) {
10 if (pHead.next != null) {
11 printList(pHead.next, result);
12 }
13 result.add(pHead.val);
14 }
15 }
16 }
2.2链表环的入口节点
边界情况：①功能测试：含环（至少需要3个节点才能有环）或不含环的链表；②边界情况：空链表
问题分解：判断是否有环？环的长度？环的入口结点？
思路：采用双指针的思想进行求解，首先采用快慢指针（p1每次走一步，p2每次走两步），若p1p2相遇则有环；然后在p1p2相遇后固定一个，让另一个继续遍历计数，再次相遇则可得到环的长度K；最后双指针隔K个先后向后遍历，p1p2相遇的位置即为入口节点。
O(N)的时间复杂度
1 public class Solution {
2
3 public ListNode EntryNodeOfLoop(ListNode pHead)
4 {
5 if (pHead == null) return null;
6 ListNode p1 = pHead;
7 if (p1.next == null || p1.next.next == null) {
8 return null;
9 }
10 ListNode p2 = pHead.next.next;
11 while (p2.next != null && p2.next.next != null) {
12 if (p2 != p1) {
13 p1 = p1.next;
14 p2 = p2.next.next;
15 } else {
16 int loopLength = 1;
17 p1 = p1.next;
18 while (p1 != p2) {
19 p1 = p1.next;
20 loopLength++;
21 }
22 p1 = pHead;
23 p2 = pHead;
24 while (loopLength-- > 0) {
25 p1 = p1.next;
26 }
27 while (p1 != p2) {
28 p1 = p1.next;
29 p2 = p2.next;
30 }
31 return p1;
32 }
33 }
34 return null;
35 }
36 }
2.3删除有序链表中重复元素
1->2->3->3->4->4->5 输出 1->2->5
边界情况：①功能测试：重复节点存在（不同位置），链表无重复节点；②边界情况：空链表或全是重复节点
思路：由于需要删除节点，故而需要保持链表不断链需要一直记录当前节点前驱位置；判断当前位置与其之后位置的元素是否相同，相同则需要进行删除。
O(N)的时间复杂度--遍历了一次链表
1 import java.util.*;
2 public class Solution {
3 public ListNode deleteDuplication(ListNode pHead)
4 {
5 if (pHead == null) return null;
6 ListNode dummy = new ListNode(0);
7 dummy.next = pHead;
8 ListNode prev = dummy;
9 ListNode cur = pHead;
10 while (cur != null) {
11 if (cur.next == null) {
12 return dummy.next;
13 } else if (cur.next.val == cur.val) {
14 int curValue = cur.val;
15 cur = cur.next;
16 while (cur != null && cur.val == curValue) {
17 cur = cur.next;
18 }
19 if (cur == null) {
20 prev.next = null;
21 return dummy.next;
22 }
23 prev.next = cur;
24 } else {
25 prev = prev.next;
26 cur = cur.next;
27 }
28 }
29 return dummy.next;
30 }
31 }
若链表无序，则需要进行2次遍历，通过记录个元素的数量进行删除。
1 import java.util.*;
2 public class Solution {
3 public ListNode deleteDuplication(ListNode pHead)
4 {
5 if (pHead == null) return null;
6 Map<Integer, Integer> map = new HashMap<>();
7 ListNode dummy = new ListNode(0);
8 dummy.next = pHead;
9 ListNode tmp = pHead;
10 while (tmp != null) {
11 if (map.containsKey(tmp.val)) {
12 map.put(tmp.val, map.get(tmp.val) + 1);
13 } else {
14 map.put(tmp.val, 1);
15 }
16 tmp = tmp.next;
17 }
18 ListNode prev = dummy;
19 ListNode cur = pHead;
20 while (cur != null) {
21 if (map.get(cur.val) > 1) {
22 prev.next = cur.next;
23 } else {
24 prev = prev.next;
25 }
26 cur = cur.next;
27 }
28 return dummy.next;
29 }
30 }