链表

一、基本概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；

链表和数组内存分布

链表存在多种形式。包括循环链表，单链表，双向链表，静态链表。

二、循环链表

2.1、基本实现和特性：

1、尾结点指针指向头结点的链表
2、可以是单链表，也可以是双链表

循环链表

2.2、总结

1、优点是从链尾到链头十分方便。
2、经典问题：约瑟夫问题。
例题1：83. 删除排序链表中的重复元素https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

三、单链表

3.1、基本实现和特性

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域，只有一个后继结点。

单链表示意图

3.2、重点概念

头结点， 尾结点

3.3、操作

3.3.1、建立链表：本质上就是不断的插入结点。
3.3.2、插入结点：就是申请空间，得到数据，建立链接的循环处理过程。
1、重点考虑相邻结点的指针改变，推荐画图法。
2、在指定指针的情况下插入结点，时间复杂度O（1），分为头插法和尾插两种。
3、如果没有指定指针的时候，则需要遍历先确定插入位置，再执行2，时间复杂度O（n）
4、注意头结点的插入

单链表头插法、尾插法
3.3.3、删除结点：
1、删除结点中“值为给定某个值”的结点，时间复杂度O（1）。
2、删除给定指针的结点，需要遍历前驱结点，时间复杂度O（n）。
3、注意删除头结点，尾结点，推荐画图法。
删除结点

3.3.4、和数组性能比较：

和数组性能对比

3.3.5、查找结点：
1、根据指针依次查找，直到找到相应的结点（考虑多个的情况）
2、时间复杂度O（n）

四、双向链表

4.1、基本概念和特性：
单向链表只有一个方向，结点只有一个后继指针next指向后面的结点，双向链表支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点，占用更多空间的同时，插入和删除效率更高。

双向链表

4.2、操作：
1、删除给定指针指向的结点，直接获取前驱结点，不需要遍历，时间复杂度为O（1），插入的情况类似删除
2、实际使用例子：java的LinkedHashMap
3、空间换时间的思想

五、静态链表

5.1、基本概念和特征：
用数组描述的链表，称为静态链表。
首先让数组的元素都是由两个数据域构成，data和cur，也就是说每一个数组的下标都要对应一个data和一个cur。
数据域data用来存放数据元素，也就是通常我们要处理的数据，而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫做游标。

5.2、示例图：

静态链表

六、常见面试题：

例题1：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

思路：

链表中删除元素，即操作指针指向下一个元素，跳过当前元素，即完成删除操作。

时间复杂度：O（n），n为节点的个数
空间复杂度：O（1）

代码实现：

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

例题2：从尾到头打印链表 https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

思路：
思路：循环head节点，指针移动到下一位，直到head为空

时间复杂度：O（n），n为节点的个数
空间复杂度：O（1）

代码实现：

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        res = []
        while head:
            res.append(head.val)
            head = head.next
        return res[::-1]

例题3：21. 合并两个有序链表 https://leetcode-cn.com/problems/merge-two-sorted-lists/

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

示例 1：

image

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

思路：

递归，判断l1和l2的值的大小，如果l1的val小，则l1指向l1和l2的合并后的结果，反之，则l2指向l1和l2的合并后的结果

时间复杂度：O（n），n为l1和l2的节点的个数
空间复杂度：O（1）

代码实现：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l2.next, l1)
            return l2

例题4： 24. 两两交换链表中的节点https://leetcode-cn.com/problems/swap-nodes-in-pairs/

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

image

输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：

输入：head = []
输出：[]
示例 3：

输入：head = [1]
输出：[1]

思路：

增加前指针指向本身，交换a，b元素，依次循环下去，返回前指针
T：O（n），n为节点的个数， S：O（1）

image

时间复杂度：O（n），n为节点的个数
空间复杂度：O（1）

代码实现：

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        pre, pre.next = self, head
        while pre.next and pre.next.next:
            a = pre.next
            b = a.next
            pre.next, a.next, b.next = b, b.next, a
            pre = a
        return self.next

撰写记录
2020.12.26-08:00:00-第一次撰写
2021.01.05-07:30:00-第二次撰写
2021.01.09-11:08:10-第三次撰写
2021.02.09-21:56:00-第四次撰写