链表专题总结
链表
链表(Linked List)是一种常见的基础数据结构,是一种线性数据结构,每个节点元素是一个单独的对象,在每一个节点里存指向下一个节点的指针(Pointer)。
链表不必须按顺序存储,链表在插入的时候可以达到 O(1) 的复杂度,但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间。
链表相关题型
与链表相关的题目,核心就是如何通过修改链表中指向下一个节点的指针来实现目标。
由于链表是不按顺序存储的线性结构,通常会通过设置额外的指针变量来记录元素的位置。
1. 链表操作
1.1 删除链表中的节点
剑指 Offer 18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。
返回删除后的链表的头节点。
1 | /** |
Leetcode 83. 删除排序链表中的重复元素
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
1 | /** |
Leetcode 19. 删除链表的倒数第 N 个节点
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
1 | /** |
1.2 链表中节点的交换
Leetcode 24. 两两交换链表中的节点
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
解题思路:
主要是指针指向的变换,搞清楚指针指向哪些元素
1 | public ListNode swapPairs(ListNode head) { |
Leetcode 328. 奇偶链表
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。
请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。
你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
1 | // 拆成两部分,再链接到一起 |
2. 环形链表
双指针
Leetcode 141. 环形链表
给定一个链表,判断链表中是否有环。
解题思路:
设置两个指针,一个一次走一步,一个一次走两步,如果慢指针追上了快指针,说明存在环。
1 | public boolean hasCycle(ListNode head) { |
3. 相交链表
Leetcode 160. 相交链表
编写一个程序,找到两个单链表相交的起始节点。
解题思路
分别设置两个指针,沿着两个链表的头开始走,再次相遇的时候的节点就是两个单链表的交点。
假设链表 A 交点之前的长度是 a,B 是 b,公共长度是 c,那么 a + c + b = b + c + a
1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |
4. 链表反转
链表的反转包括最简单的逆序反转,还有 k 个一组反转链表
Leetcode 206. 反转链表
1 | public ListNode reverseList(ListNode head) { |
Leetcode 25. K 个一组翻转链表
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例:
给你这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
迭代方法
1 | /** |
递归方法
1 | public ListNode reverseKGroup(ListNode head, int k) { |
5. 链表合并
5.1 归并链表
Leetcode 21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
迭代方法
1 | public ListNode mergeTwoLists(ListNode l1, ListNode l2) { |
递归方法
1 | public ListNode mergeTwoLists(ListNode l1, ListNode l2) { |
Leetcode 23. 合并K个升序链表
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
解题思路
两两合并链表的扩充版,先两两合并,再合并总体的。
1 | public ListNode mergeKLists(ListNode[] lists) { |
借助堆
将链表的头节点放在一个小顶堆当中,每次从堆中取元素,加到结果列表中
1 | public ListNode mergeKLists(ListNode[] lists) { |
5.2 链表相加
两个链表相加,不反转
Leetcode 2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
1 | public ListNode addTwoNumbers(ListNode l1, ListNode l2) { |
Leetcode 445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。
1
2 输入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 8 -> 0 -> 7
一种思路是分别反转两个链表,然后对应相加,最后再进行反转,或者直接采用头插法得到结果链表。
进阶版:如果不进行反转的话,可以借助栈这种数据结构,来实现与链表反转同样的功能。
1 | public ListNode addTwoNumbers(ListNode l1, ListNode l2) { |
6. 综合题目
综合题目一般会综合运用链表反转,快慢指针等技巧
Leetcode 143. 重排链表
给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
解题思路:
- 快慢指针找中点
- 反转后半部分链表
- 归并重新链接
1 | public void reorderList(ListNode head) { |
Leetcode 234. 回文链表
请判断一个链表是否为回文链表。
解题思路
- 快慢指针找中点
- 反转后半部分链表
- 比较两个部分
1 | public boolean isPalindrome(ListNode head) { |
总结
链表的题目并不难,最重要的是搞清楚指针应该如何修改指向,达到目的。画画图会比较清晰。
技巧:
快慢指针
链表反转
pre 指针,next 指针
- 本文作者: Kelly Liu
- 本文链接: http://tiantianliu2018.github.io/2020/10/23/链表专题总结/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!