最近在刷关于链表的题目，特开一贴记录有意思的相关题目。

介绍

尾插法“新建”链表的思路可以解决绝大多数链表题目。

链表题目：第一反应就应该是头节点是否被操作，要不要dummy虚拟头节点方便操作。

尾插法“新建”链表思路：不要在原链表上进行指针操作，只需要原链表上的「满足题意」的节点“拆”下，然后拼接在新链表上。（注意：此处新建非重新malloc节点，而是修改原链表结点的指针指向。）

因此在解决链表一类问题时，如果想不到巧妙地递归方法，就用迭代。使用迭代脑海里就要有“原链表”和“新链表”这两个链表，因此题意就可以转换为如何筛选出“原链表”符合题意的节点并连在“新链表”上[1]。

1. lc 82 - 删除排序链表中的重复元素 II

  • 题目来源
  • 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
  • 难度：中等

1.1 解题思路 - 迭代

最近对递归的做法较为熟练，但迭代反而不熟练。这是一道用迭代完成的题目。下面是步骤。

  1. 与链表的其他题目类似，为了防止删除头结点的极端情况发生，先创建空结点dummy，使dummy指向传入的head结点。
  2. 然后创建cur的指针，指向链表的头部（即cur = dummy）。
  3. 进入while循环：接着对cur指针迭代，因为要对比cur(cur最初始的定义指向空结点)指针的下一个结点与下下一个结点的值是否相等，为了防止产生空指针异常，故退出while循环迭代的条件为：cur.next and cur.next.next。此时创建一个临时指针tmp，指向cur的下一个节点。
  • 3.1 在迭代过程中，如果cur.next.val == cur.next.next.val说明此时有重复元素，临时指针tmp发挥作用：将推进链表的迭代，而cur指针停止移动，即tmp指向的第一个重复元素所在的位置。
    • 3.1.1 通过一个内部的while循环去重。若tmp指针的结点与下一个结点的值是相等，则直接将tmp指向下一节点，向后迭代即可。反之，不等时，便可去重。此时tmp指向的是重复元素中的便是最后一个位置。最后cur.next = temp.next就实现了消除重复元素。
  • 3.2 如果cur.next.val != cur.next.next.val说明此时cur后面两个节点不是有重复元素，cur向后迭代。
  1. 迭代完成后，返回dummy的next。

1.2 时间复杂度

  • 时间复杂度： O(n)。看似两层循环，其实内层循环和外层循环的迭代路径是互补的，本质上只遍历一次链表就结束。
  • 空间复杂度： O(1)。

1.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head: return head
        dummy_node = ListNode(0)
        dummy_node.next = head 
        cur = dummy_node
        while cur.next and cur.next.next:
            tmp = cur.next
            if tmp.val == tmp.next.val:
                while tmp.next and tmp.val == tmp.next.val:
                    tmp = tmp.next
                cur.next = tmp.next
            else:
                cur = cur.next
        return dummy_node.next

2. 剑指 Offer 35 - 复杂链表的复制

  • 题目来源
  • 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
  • 难度：中等

2.1 解题思路 - 哈希表 + 链表

2.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return head
        hashmap = dict()
        # 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        cur = head
        while cur:
            hashmap[cur] = Node(cur.val)
            cur = cur.next
        # 4. 构建新节点的 next 和 random 指向
        cur = head
        while cur:
            hashmap[cur].next = hashmap.get(cur.next) # 新链表中cur位置上node的next指向 新链表中cur.next位置上node
            hashmap[cur].random = hashmap.get(cur.random) # 新节点random指向随机的新节点
            cur = cur.next
        # 5. 返回新链表的头节点
        return hashmap[head]

相关题目

更多链表题目请搜索tags下的链表。

参考

[1] boille. 通用思路解决链表问题. https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/tong-yong-si-lu-jie-jue-lian-biao-wen-ti-xaeu/

[2] keithy. JAVA “哑结点 + 非递归” 容易理解，用时1ms. https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/java-ya-jie-dian-fei-di-gui-rong-yi-li-jie-yong-sh/

[3] jyd. 剑指 Offer 35. 复杂链表的复制（哈希表 / 拼接与拆分，清晰图解）. https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-/