链表 Linked List

有单链表（singly linked list）和双向链表(doubly linked list)，主要考察单向链表，双向链表一般比较简单。

基本操作

写链表class（ADT）：单链表、双向链表、长度、尾节点等特性都会写。
虚拟头（dummy head）：可以保证能找到链表头在哪，防止原链表头删了等，遍历的时候也不用特殊处理链表头，方便
添加任意index的node：要注意怎么添加链表头和尾（index = 0）
删除任意index的node：要注意怎么删除链表头
反转链表

标准迭代答案，就用while node:和一个newHead（或者叫last、prev），不要用while node.next:！\ 记住上面是2行，while里面是4行！

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
   def reverseList(self, head: ListNode) -> ListNode:
       # 迭代
       newHead = None
       node = head
       while node:
           next = node.next
           node.next = newHead
           newHead = node
           node = next
       return newHead

标准递归答案，有点难想，多做加记忆！

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 递归
        if not head or not head.next:
            return head
        newHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newHead

双指针

单链表只能是同向指针，但是灵活运用多个快慢指针，有奇效。

在不知道总长的情况下，找倒数第i个元素、找中间等
链表找环入口
找两个链表相交点

LeetCode

#	题名	难度	标签	备注
707	设计链表 Design Linked List	中等	链表	细节总是写不对，要多注意和练习。单双链表都要会。
141	环形链表 Linked List Cycle	简单	双指针	可以用快慢指针，但直接标记已扫过的也行。
142	环形链表二 Linked List II	中等	双指针	不允许该原来的链表，不用哈希表的话只能用快慢指针了。从零做的话是需要数学推导计算怎么找环的入口的。但从做题角度，可以记住这个套路，考官要求推的时候记得推就行。
160	相交链表 Intersection of Two Linked Lists	中等	双指针	双指针，也可以记忆。两个同速指针同时分别从两个链表头出发，不相交则末尾不等，否则相交。若相交，走完了去走另一个链表，相交时路程等长。
19	删除链表的倒数第 N 个结点 Remove Nth Node From End of List	中等	双指针	两个指针差n。
206	反转链表 Reverse Linked List	简单	链表	基本操作，要熟练。
203	移除链表元素 Remove Linked List Element	简单	链表	基本操作，要熟练。
328	奇偶链表 Odd Even Linked List	中等	链表	应该算简单，基本操作。
234	回文链表 Palindrome ([ˈpalɪndrəʊm]) Linked List	中等	链表	找中间、反转尾部。
21	合并两个有序链表 Merge Two Sorted Lists	简单	链表	基本操作。
61	Rotate List	中等	链表	应该算简单题，只是取余数然后拼接数组。虽然是两个指针，但并不依赖双指针解题，只是方便操作。