1、删除链表中重复的节点
在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留，返回链表头指针，例如链表1-2-3-3-4-4-5 处理后为1-2-5
反转链表
思路：需要有一个变量用来存放cur.next,需要定义一个pre指针
判断链表是否有环
思路：快慢指针 假如两个指针相遇则说明有环
判断链表是否有环，假如有环返回第一个入环节点
思路：快慢指针，先判断是否有环，然后将fast移到head 再进行遍历，直到他们相等
合并两个有序链表，使其仍然有序
思路：定义一个伪头结点，然后比较p1和p2的值，将p3的next指向较小的那个
链表中倒数第k个节点
思路：双指针，p2先走k步，p1和p2间的距离为k 直到p2走到最后一位，p1指向的就是倒数第k个节点
删除链表的节点
思路：首先定位到需要删除的节点，然后存储前置节点，将前置节点的next指向当前节点的next即可删除当前节点
删除链表的倒数第n个节点
思路：根据查找链表的倒数第k个节点知道双指针法，慢指针指向的就是要删除的那个数
根据删除链表节点知道，需要知道前置节点才能进行删除
因此采用哑节点，即增加一个头结点，慢指针指向哑结点，快指针指向头结点，然后遍历，慢指针最后指向的就是被删除数的前一个数
两个链表的第一个公共节点/判断两个链表是否相交
思路：双指针，node1到达headA结尾时，到headB继续遍历 node2到达headB结尾时，到headA继续遍历，两个节点相遇，则为第一个公共节点
两个链表相加，有进位的时候下一个节点需要加上进位
思路：遍历链表，假如最后一位进位大于0，则新建一个节点，哑节点的引入
LRU缓存：
思路：利用哈希表+双向链表
双向链表按照使用顺序存储键值对，靠近头部的键值是最近使用的，靠近尾部的键值对是最久未使用的
哈希表通过缓存数据的键映射到其在双向链表中的位置
首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在O(1)时间内完成get或者put操作
对于get方法，首先判断key是否存在
如果key不存在，返回-1
如果key存在，则key对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值
对于put操作，首先判断key是否存在：
如果key不存在，使用key和value创建一个新的节点，在双线链表的头部添加该节点，并将key和该节点添加进哈希表中，然后判断链表节点数是否超出容量，如果超过，则删除尾部节点，并删除哈希表中对应的项
如果key存在，则与get操作类似，先通过表定位，再将对应节点值更新为value，并将该节点移动到双向链表的头部
class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cache = dict()
# 使用伪头部和伪尾部节点
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.size = 0
def get(self, key: int) -> int:
if key not in self.cache:
return -1
# 如果 key 存在，先通过哈希表定位，再移到头部
node = self.cache[key]
self.moveToHead(node)
return node.value
def put(self, key: int, value: int) -> None:
if key not in self.cache:
# 如果 key 不存在，创建一个新的节点
node = DLinkedNode(key, value)
# 添加进哈希表
self.cache[key] = node
# 添加至双向链表的头部
self.addToHead(node)
self.size += 1
if self.size > self.capacity:
# 如果超出容量，删除双向链表的尾部节点
removed = self.removeTail()
# 删除哈希表中对应的项
self.cache.pop(removed.key)
self.size -= 1
else:
# 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node = self.cache[key]
node.value = value
self.moveToHead(node)
def addToHead(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def removeNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def moveToHead(self, node):
self.removeNode(node)
self.addToHead(node)
def removeTail(self):
node = self.tail.prev
self.removeNode(node)
return node
