[Leetcode][链表]相关题目汇总/分析/总结

阳光穿透心脏的1/2处 2022-06-09 01:18 192阅读 0赞

## 题目汇总 ##

以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。

目前范围：Leetcode前150题

### 单链表 ###

*  [Reverse Linked List/Reverse Linked List II][Reverse Linked List_Reverse Linked List II]  
    翻转链表（必考）
 *  [Add Two Numbers][]  
    给定两个链表分别代表两个非负整数。数位以倒序存储，并且每一个节点包含一位数字。将两个数字相加并以链表形式返回。
 *  [Remove Nth Node From End of List][]  
    删除链表中倒数第n个节点
 *  [Merge Two Sorted Lists][]  
    合并两个排好序的链表，作为新链表
 *  [Merge K Sorted Lists][]  
    将k个排序好的链表合并成新的有序链表
 *  [Swap Nodes in Pairs][]  
    交换链表中相邻的两个元素
 *  [Reverse Nodes in k-Group][]  
    将一个链表中每k个数进行翻转，末尾不足k个的数不做变化。  
    是上一题的升级版。
 *  [Rotate List][]  
    将一个链表中的元素向右旋转k个位置。
 *  [删除排序链表中的重复元素/删除排序链表中的重复元素 II][II]  
    删除一个有序链表中重复的元素，使得每个元素只出现一次。/ 把一个有序链表中所有重复的数字全部删光，删除后不再有原先重复的那些数字。
 *  [Partition List/分隔链表][Partition List]  
    给定一个链表以及一个目标值，把小于该目标值的所有节点都移至链表的前端，大于或等于目标值的节点移至链表的尾端，同时要保持这两部分在原先链表中的相对位置。
 *  [Populating Next Right Pointers in Each Node I and II/填充同一层的兄弟节点][Populating Next Right Pointers in Each Node I and II]  
    为二叉树的节点都添加一个next指针，指向跟它在同一高度的右边的节点，如果右边没有节点，就指向None。/ 二叉树并不都是满二叉树
 *  [Copy List with Random Pointer/复制带随机指针的链表][Copy List with Random Pointer]  
    一个链表中的每一个节点都有一个额外的随机指针，指向链表中的任意节点或空节点。对这个链表进行深拷贝。（要拷贝随机指针）
 *  [Linked List Cycle/Linked List Cycle II/环形链表/环形链表 II][Linked List Cycle_Linked List Cycle II_ II]  
    判断一个链表中是否存在着一个环，能否在不申请额外空间的前提下完成？/ 如果给定的单向链表中存在环，则返回环起始的位置，否则返回为空。最好不要申请额外的空间。
 *  [Reorder List/重排链表][Reorder List]  
    将单向链表L0→L1→…→Ln-1→Ln转化为L0→Ln→L1→Ln-1→L2→Ln-2→…的形式，也就是从头部取一个节点，从尾部取一个节点，直到将原链表转化成新的链表。
 *  [Insertion Sort List/对链表进行插入排序][Insertion Sort List]  
    通过插入排序的方法排序一个链表。
 *  [Sort List/排序链表][Sort List]  
    在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

## 链表总结 ##

*  Dummy node 是一个虚拟节点，也可以认为是标杆节点。Dummy node 就是在链表表头 head 前加一个节点指向 head，即 dummy -> head。

> Dummy node的使用多针对单链表没有前向指针的问题，保证链表的 head 不会在删除操作中丢失。
> 
> 除此之外，还有一种用法比较少见，就是使用 dummy node 来进行head的删除操作，比如 Remove Duplicates From Sorted List II，一般的方法current = current.next 是无法删除 head 元素的，所以这个时候如果有一个dummy node在head的前面。
> 
> 所以，当链表的 head 有可能变化（被修改或者被删除）时，使用 dummy node 可以很好的简化代码，最终返回 dummy.next 即新的链表。  
> \- **除了dummy外，实际操作链表（比如遍历过去时），不要去修改dummy，而是用current = dummy，去操作current向后遍历。**

*  在操作链表时，通常在讲链表赋值给变量时，并不是新建链表，而是在原链表上操作地址。
 *  单链表Python定义：

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

[Reverse Linked List_Reverse Linked List II]: https://blog.csdn.net/qqxx6661/article/details/78399046
[Add Two Numbers]: http://blog.csdn.net/qqxx6661/article/details/75142501
[Remove Nth Node From End of List]: http://blog.csdn.net/qqxx6661/article/details/77518854
[Merge Two Sorted Lists]: http://blog.csdn.net/qqxx6661/article/details/77489334
[Merge K Sorted Lists]: http://blog.csdn.net/qqxx6661/article/details/77814794
[Swap Nodes in Pairs]: http://blog.csdn.net/qqxx6661/article/details/77846973
[Reverse Nodes in k-Group]: http://blog.csdn.net/qqxx6661/article/details/77847254
[Rotate List]: http://blog.csdn.net/qqxx6661/article/details/78221500
[II]: http://blog.csdn.net/qqxx6661/article/details/78336642
[Partition List]: http://blog.csdn.net/qqxx6661/article/details/78360395
[Populating Next Right Pointers in Each Node I and II]: http://blog.csdn.net/qqxx6661/article/details/78456278
[Copy List with Random Pointer]: http://blog.csdn.net/qqxx6661/article/details/78588471
[Linked List Cycle_Linked List Cycle II_ II]: http://blog.csdn.net/qqxx6661/article/details/78685674
[Reorder List]: http://blog.csdn.net/qqxx6661/article/details/78817958
[Insertion Sort List]: http://blog.csdn.net/qqxx6661/article/details/78818256
[Sort List]: http://blog.csdn.net/qqxx6661/article/details/81773447