算法面试题 | 链表问题总结

作者: 彭旭锐 | 来源:发表于2020-10-12 02:09 被阅读0次

前言

链表的相关问题，在面试中出现频率较高，这些问题往往也是解决其他复杂问题的基础；
在这篇文章里，我将梳理链表问题的问题 & 解法。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

系列文章

延伸文章

算法面试题 | 高楼丢鸡蛋（源自谷歌面试题）

`删除链表节点`	提示 & 题解
203. 移除链表元素 Remove Linked List Elements	【题解】
237. 删除链表中的节点 Delete Node in a Linked List	【题解】
19. 删除链表的倒数第N个节点 Remove Nth Node From End of List	【题解】
86. 分隔链表 Partition List	【题解】
328. 奇偶链表 Odd Even Linked List	【题解】
83. 删除排序链表中的重复元素 Remove Duplicates from Sorted List
82. 删除排序链表中的重复元素 II Remove Duplicates from Sorted List II
725. 分隔链表 Split Linked List in Parts
（扩展）0876. 链表的中间结点 Middle of the Linked List	【题解】

`反转链表`	提示 & 题解
206. 反转链表 Reverse Linked List	【题解】
92. 反转链表 II Reverse Linked List II	【题解】
234. 回文链表 Palindrome Linked List	【题解】
25. K 个一组翻转链表 Reverse Nodes in k-Group

`合并有序链表`	提示 & 题解
21. 合并两个有序链表 Merge Two Sorted Lists	【题解】
23. 合并K个升序链表 Merge k Sorted Lists	【题解】

`排序链表`	提示 & 题解
147. 对链表进行插入排序 Insertion Sort List	【题解】
148. 排序链表 Sort List	【题解】

`环形链表`	提示 & 题解
160. 相交链表 Intersection of Two Linked Lists	【题解】
141. 环形链表 Linked List Cycle	【题解】
142. 环形链表 II Linked List Cycle II	【题解】
61. 旋转链表 Rotate List	【题解】

`其他`	提示 & 题解
24. 两两交换链表中的节点 Swap Nodes in Pairs
143. 重排链表 Reorder List
138. 复制带随机指针的链表 Copy List with Random Pointer
380. 常数时间插入、删除和获取随机元素 Insert Delete GetRandom O(1)
381. O(1) 时间插入、删除和获取随机元素 - 允许重复 Insert Delete GetRandom O(1) - Duplicates allowed
707. 设计链表 Design Linked List
430. 扁平化多级双向链表 Flatten a Multilevel Doubly Linked List
817. 链表组件 Linked List Components	【题解】

1. 概述

1.1 链表的定义

链表是一种常见的基础数据结构，是一种线性表。与顺序表不同的是，链表中的每个节点不是顺序存储的，而是通过节点的指针域指向到下一个节点。

1.2 链表的优缺点

对比	优点	缺点
内存管理	充分利用计算机内存空间，更灵活地分配内存空间	指针域增加了内存消耗
操作效率	能在 $O(1)$ 时间内删除或添加节点（前提是前驱节点已知）	失去了数组随机访问的特性，查询对应位置的节点需要 $O(n)$ 时间
数据容量	需要预先分配内存空间，容量不足需要扩容	不需要预先分配内存空间，不需要扩容
访问性能	/	CPU 缓存行无法提高效率

1.3 链表的类型

单链表、双链表、循环链表、静态链表

2. 删除链表节点

删除链表节点时，考虑到可能删除的是链表的第一个节点（没有前驱节点），为了编码方便，可以考虑增加一个 哨兵节点。其中，在删除链表的倒数第 N 个节点问题里，使用快慢指针在一趟扫描里找出倒数第 N 个节点是比较重要的编程技巧。

237. Delete Node in a Linked List 删除链表中的节点 【题解】

203. Remove Linked List Elements 移除链表元素 【题解】

不移除野指针
class Solution {
    fun removeElements(head: ListNode?, `val`: Int): ListNode? {
        // 哨兵节点
        val sentinel = ListNode(-1)
        sentinel.next = head

        var pre = sentinel
        var cur: ListNode? = sentinel
        while (null != cur) {
            if (`val` == cur.`val`) {
                // 移除
                pre.next = cur.next
            } else {
                pre = cur
            }
            cur = cur.next
        }
        return sentinel.next
    }
}

移除野指针
class Solution {
    fun removeElements(head: ListNode?, `val`: Int): ListNode? {
        // 哨兵节点
        val sentinel = ListNode(-1)
        sentinel.next = head

        var pre = sentinel
        var cur: ListNode? = sentinel
        while (null != cur) {
            val removeNode = if (`val` == cur.`val`) {
                // 移除
                pre.next = cur.next
                cur
            } else {
                pre = cur
                null
            }
            cur = cur.next
            if (null != removeNode) {
                removeNode.next = null
            }
        }
        return sentinel.next
    }
}

19. Remove Nth Node From End of List 删除链表的倒数第N个节点 【题解】

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

class Solution {
    fun removeNthFromEnd(head: ListNode, n: Int): ListNode? {
        // 哨兵节点
        val sentinel = ListNode(-1)
        sentinel.next = head

        var fast: ListNode? = sentinel
        var slow: ListNode? = sentinel

        for (index in 0 until n) {
            fast = fast!!.next
        }

        // 找到倒数第 k 个节点的前驱
        while (null != fast!!.next) {
            fast = fast.next
            slow = slow!!.next
        }
        slow!!.next = slow.next!!.next
        return sentinel.next
    }
}

复杂度分析：

时间复杂度：每个节点扫描一次，时间复杂度为 $O(n)$
空间复杂度：使用了常量级别变量，空间复杂度为 $O(1)$

类似地，876. Middle of the Linked List 链表的中间结点【题解】也是通过快慢指针来找到中间节点的：

class Solution {
    fun middleNode(head: ListNode?): ListNode? {
        if (null == head || null == head.next) {
            return head
        }
        var fast = head
        var slow = head

        while (null != fast && null != fast.next) {
            fast = fast.next!!.next
            slow = slow!!.next
        }

        return slow
    }
}

86. Partition List 分隔链表 【题解】

删除链表中等于给定值 val 的所有节点。

思路：分隔链表无非是先将大于等于 val 的节点从原链表中移除到第二个链表中，最后再拼接两个链表。

class Solution {
    fun partition(head: ListNode?, x: Int): ListNode? {
        if (null == head) {
            return null
        }

        // 哨兵节点
        val sentinel = ListNode(-1)
        sentinel.next = head
        var pre = sentinel
        // 第二链表
        var bigHead : ListNode? = null
        var bigRear = bigHead

        var cur = head
        while (null != cur) {
            if (cur.`val` >= x) {
                // 大于等于：移除
                pre.next = cur.next
                if(null == bigHead){
                    bigHead = cur
                    bigRear = cur
                }else{
                    bigRear!!.next = cur
                    bigRear = cur
                }
            } else {
                pre = cur
            }
            if (null == cur.next) {
                // 拼接
                pre.next = bigHead
                bigRear?.next = null
                break
            }
            cur = cur.next
        }
        return sentinel.next
    }
}

复杂度分析：

时间复杂度：每个节点扫描一次，时间复杂度为 $O(n)$
空间复杂度：使用了常量级别变量，空间复杂度为 $O(1)$

328. Odd Even Linked List 奇偶链表 【题解】

思路：奇偶链表无非是先将奇节点放在一个链表里，偶节点放在另一个链表里，最后把偶节点接在奇链表的尾部

class Solution {
    fun oddEvenList(head: ListNode?): ListNode? {
        if (null == head) {
            return null
        }

        var odd: ListNode = head
        var even = head.next
        val evenHead = even

        while (null != even && null != even.next) {
            // 偶节点
            odd.next = even.next
            odd = odd.next!!
            // 奇节点
            even.next = odd.next
            even = even.next
        }
        odd.next = evenHead
        // 头节点不动
        return head
    }
}

83. Remove Duplicates from Sorted List 删除排序链表中的重复元素

82. Remove Duplicates from Sorted List II 删除排序链表中的重复元素 II

3. 反转链表

反转链表问题在面试中出现频率 非常非常高，相信有过几次面试经验的同学都会同意这个观点。在这里，我找出了 4 道反转链表的问题，从简单延伸到困难，快来试试吧。

206. 反转链表 Reverse Linked List 【题解】

反转一个单链表。

解法1：递归

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        if(null == head || null == head.next){
            return head
        }
        val prefix = reverseList(head.next)
        head.next.next = head
        head.next = null
        return prefix
    }
}

复杂度分析：

时间复杂度：每个节点扫描一次，时间复杂度为 $O(n)$
空间复杂度：使用了递归栈，空间复杂度为 $O(n)$

解法2：迭代

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        var cur: ListNode? = head
        var headP: ListNode? = null

        while (null != cur) {
            val tmp = cur.next
            cur.next = headP
            headP = cur
            cur = tmp
        }
        return headP
    }
}

复杂度分析：

时间复杂度：每个节点扫描一次，时间复杂度为 $O(n)$
空间复杂度：使用了常量级别变量，空间复杂度为 $O(1)$

92. 反转链表 II Reverse Linked List II 【题解】

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

class Solution {
    fun reverseBetween(head: ListNode?, m: Int, n: Int): ListNode? {
        if (null == head || null == head.next) {
            return head
        }

        // 哨兵节点
        val sentinel = ListNode(-1)
        sentinel.next = head
        var rear = sentinel

        // 1. 找到反转开始位置前驱节点
        var cur = sentinel
        for (index in 0 until m - 1) {
            cur = cur.next!!
            rear = cur
        }

        // 2. 反转指定区域
        rear.next = reverseList(rear.next!!, n - m + 1)
        return sentinel.next
    }

    /**
     * 反转指定区域
     * @param size 长度
     */
    fun reverseList(head: ListNode, size: Int): ListNode? {
        var cur: ListNode? = head
        var headP: ListNode? = null
        // 反转的起始点需要连接到第 n 个节点
        val headTemp = head

        var count = 0
        while (null != cur && count < size) {
            val tmp = cur.next
            cur.next = headP
            headP = cur
            cur = tmp

            count++
        }

        // 连接到第 n 个节点
        headTemp.next = cur
        return headP
    }
}

复杂度分析：

时间复杂度：每个节点扫描一次，时间复杂度为 $O(n)$
空间复杂度：使用了常量级别变量，空间复杂度为 $O(1)$

234. Palindrome Linked List 回文链表 【题解】

请判断一个链表是否为回文链表。

思路：使用快慢指针找到中间节点，反转后半段链表（基于反转链表 II），比较前后两段链表是否相同，最后再反转回复到原链表。

class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        if (null == head || null == head.next) {
            return true
        }

        // 1. 找到右边中节点（右中节点）
        var fast = head
        var slow = head

        while (null != fast && null != fast.next) {
            slow = slow!!.next
            fast = fast.next!!.next
        }

        // 2. 反转后半段
        val reverseP = reverseList(slow!!)

        // 3. 比较前后两段是否相同
        var p = head
        var q: ListNode? = reverseP
        var isPalindrome = true

        while (null != p && null != q) {
            if (p.`val` == q.`val`) {
                p = p.next
                q = q.next
            } else {
                isPalindrome = false
                break
            }
        }

        // 4. 恢复链表
        reverseList(reverseP)
        return isPalindrome
    }

    /**
     * 反转链表
     */
    private fun reverseList(head: ListNode): ListNode {
        // 略，见上一节...
    }
}

复杂度分析：

时间复杂度：每个节点扫描两次，时间复杂度为 $O(n)$
空间复杂度：使用了常量级别变量，空间复杂度为 $O(1)$

25. K 个一组翻转链表 Reverse Nodes in k-Group

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

4. 合并有序链表

合并有序链表问题在面试中出现频率较高，其中，合并两个有序链表 是比较简单的，而它的进阶版 合并K个升序链表 要考虑的因素更全面，难度也有所增强，快来试试吧。

21. Merge Two Sorted Lists 合并两个有序链表 【题解】

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution {
    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        if (null == l1) return l2
        if (null == l2) return l1

        // 哨兵节点
        val sentinel = ListNode(-1)
        var rear = sentinel

        var p = l1
        var q = l2

        while (null != p && null != q) {
            if (p.`val` < q.`val`) {
                rear.next = p
                rear = p
                p = p.next
            } else {
                rear.next = q
                rear = q
                q = q.next
            }
        }
        rear.next = if (null != p) p else q

        return sentinel.next
    }
}

复杂度分析：

时间复杂度：每个节点扫描一次，时间复杂度为 $O(m + n)$
空间复杂度：使用了常量级别变量，空间复杂度为 $O(1)$

23. Merge k Sorted Lists 合并K个升序链表 【题解】

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

解法1：暴力法

思路1：与合并两个有序链表类似，每轮从 k 个链表中取出最小的节点，并插入结果链表中。其中，从 k 个数中取出最小节点的时间复杂度为 $O(k)$ 。

思路2：这个思路与上个思路类似，时间复杂度和空间复杂度页相同，即：依次将 k 个链表与结果链表合并。

略

复杂度分析：

时间复杂度： $O(nk * k)$
空间复杂度： $O(1)$

解法2：排序法

思路：用一个数组保存所有节点之后，进行快速排序，随后将数组输出单链表。

class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        if (lists.isNullOrEmpty()) {
            return null
        }
        // 1. 用一个数组保存所有节点
        val array = ArrayList<ListNode>()
        for (list in lists) {
            var cur = list
            while (null != cur) {
                array.add(cur)
                cur = cur.next
            }
        }
        // 2. 快速排序
        array.sortWith(Comparator { node1, node2 -> node1.`val` - node2.`val` })
        // 3. 输出为链表
        val newHead = ListNode(-1)
        var rear = newHead
        for (node in array) {
            rear.next = node
            rear = node
        }
        return newHead.next
    }
}

复杂度分析：

时间复杂度：合并节点时间 $O(nk)$ ，快速排序时间 $O(nk*lgnk)$ ，输出单链表时间 $O(nk)$ ，总体时间复杂度 $O(nk*lgnk)$
空间复杂度：使用数组空间 $O(nk)$

解法3：归并法

思路：将 k 组链表分为两部分，然后递归地处理两组链表，最后再合并起来。

class Solution {

    // 合并 k 个有序链表
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        if (lists.isNullOrEmpty()) {
            return null
        }
        return mergeKLists(lists, 0, lists.size - 1)
    }

    fun mergeKLists(lists: Array<ListNode?>, left: Int, right: Int): ListNode? {
        if (left == right) {
            return lists[left]
        }
        // 归并
        val mid = (left + right) ushr 1
        return mergeTwoLists(
            mergeKLists(lists, left, mid),
            mergeKLists(lists, mid + 1, right)
        )
    }

    // 合并两个有序链表
    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        // 略，见上一节...
    }
}

复杂度分析：

时间复杂度：时间主要在合并链表的操作上，从递归树可以看出，递归树每一层的节点个数都是 $nk$ ，而递归树的高度 $h = lgk$ ，因此总的时间复杂度为 $O(nk*lgk)$
空间复杂度：使用了递归栈，空间复杂度为 $O(lgk)$

解法4：小顶堆法

思路：在解法1中，从 k 个数中取出最小节点的时间复杂度为 $O(k)$ ，可以使用最小堆（优先队列）来优化到 $O(lgk)$ 。其中，堆内节点始终是 k 个链表的未处理部分的表头。

class Solution {

    // 合并 k 个有序链表
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        if (lists.isNullOrEmpty()) {
            return null
        }

        // 最小堆
        val queue = PriorityQueue<ListNode>(lists.size) { node1, node2 -> node1.`val` - node2.`val` }

        // 1. 建堆
        for (list in lists) {
            if (null != list) {
                queue.offer(list)
            }
        }

        val sentinel = ListNode(-1)
        var rear = sentinel

        // 2. 出队
        while (queue.isNotEmpty()) {
            val node = queue.poll()!!
            // 输出到结果链表
            rear.next = node
            rear = node
            // 存在后继节点，加入堆中
            if (null != node.next) {
                queue.offer(node.next)
            }
        }
        return sentinel.next
    }
}

复杂度分析：

时间复杂度：大小为 k 的二叉堆建堆时间为 $O(k)$ ，取堆顶的时间为 $O(1)$ ，插入一个新节点的时间为 $O(lgk)$ ，总体时间复杂度为 $O(nk∗lgk)$
空间复杂度：二叉堆空间为 $O(k)$

5. 排序链表

147. Insertion Sort List 对链表进行插入排序 |【题解】

148. Sort List 排序链表 【题解】

6. 环形链表

链表相交 & 成环问题可以归为一类问题，在面试中出现频率较高；在之前的一篇文章里，我们单独讨论过：《算法面试题 | 链表相交 & 成环问题》

感谢喜欢！你的点赞是对我最大的鼓励！欢迎关注彭旭锐的GitHub！

网友评论

本文标题：算法面试题 | 链表问题总结

本文链接：https://www.haomeiwen.com/subject/hooypktx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

算法面试题 | 链表问题总结

前言

系列文章

延伸文章

目录

1. 概述

1.1 链表的定义

1.2 链表的优缺点

1.3 链表的类型

2. 删除链表节点

237. Delete Node in a Linked List 删除链表中的节点 【题解】

203. Remove Linked List Elements 移除链表元素 【题解】

19. Remove Nth Node From End of List 删除链表的倒数第N个节点 【题解】

86. Partition List 分隔链表 【题解】

328. Odd Even Linked List 奇偶链表 【题解】

83. Remove Duplicates from Sorted List 删除排序链表中的重复元素

82. Remove Duplicates from Sorted List II 删除排序链表中的重复元素 II

3. 反转链表

206. 反转链表 Reverse Linked List 【题解】

92. 反转链表 II Reverse Linked List II 【题解】

234. Palindrome Linked List 回文链表 【题解】

25. K 个一组翻转链表 Reverse Nodes in k-Group

4. 合并有序链表

21. Merge Two Sorted Lists 合并两个有序链表 【题解】

23. Merge k Sorted Lists 合并K个升序链表 【题解】

5. 排序链表

147. Insertion Sort List 对链表进行插入排序 |【题解】

148. Sort List 排序链表 【题解】

6. 环形链表

推荐阅读

感谢喜欢！你的点赞是对我最大的鼓励！欢迎关注彭旭锐的GitHub！

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Android开发经验谈

数据结构和算法分析