【Leetcode】【链表】相关题目汇总 分析 总结

题目汇总

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

目前范围：Leetcode前150题

单链表

• 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
  删除一个有序链表中重复的元素，使得每个元素只出现一次。/ 把一个有序链表中所有重复的数字全部删光，删除后不再有原先重复的那些数字。

• 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