链表问题集锦

链表问题集锦

• 面试精选：链表问题集锦

常见问题（所有类型题目Leetcode均有）：

• 单链表转置（递归，非递归）
• 每K个节点反转链表（方法同上，变量多一点）
• 寻找或删除链表倒数第k个节点（一次遍历，双指针)
• 求链表中间节点（一次遍历，快慢指针）
• 判断链表是否有环并找到入口点（O(1)空间，快慢指针+数学推导）
• 判断无环链表相交（一次遍历，尾节点相同）
• 判断有环链表相交（判断环，环内任意节点相同）
• 两链表相交的第一公共点（两次遍历求长度差，双指针）
• 复制带有随机指针的链表，复制有向图（O(1)空间，有效利用已有信息）