题目汇总
以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。
目前范围：Leetcode前150题
单链表
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
删除一个有序链表中重复的元素，使得每个元素只出现一次。/ 把一个有序链表中所有重复的数字全部删光，删除后不再有原先重复的那些数字。Partition List/分隔链表
给定一个链表以及一个目标值，把小于该目标值的所有节点都移至链表的前端，大于或等于目标值的节点移至链表的尾端，同时要保持这两部分在原先链表中的相对位置。Populating Next Right Pointers in Each Node I and II/填充同一层的兄弟节点
为二叉树的节点都添加一个next指针，指向跟它在同一高度的右边的节点，如果右边没有节点，就指向None。/ 二叉树并不都是满二叉树Copy List with Random Pointer/复制带随机指针的链表
一个链表中的每一个节点都有一个额外的随机指针，指向链表中的任意节点或空节点。对这个链表进行深拷贝。（要拷贝随机指针）Linked List Cycle/Linked List Cycle II/环形链表/环形链表 II
判断一个链表中是否存在着一个环，能否在不申请额外空间的前提下完成？/ 如果给定的单向链表中存在环，则返回环起始的位置，否则返回为空。最好不要申请额外的空间。Reorder List/重排链表
将单向链表L0→L1→…→Ln-1→Ln转化为L0→Ln→L1→Ln-1→L2→Ln-2→…的形式，也就是从头部取一个节点，从尾部取一个节点，直到将原链表转化成新的链表。Insertion 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
京公网安备 11010502036488号