数据结构与算法:线性表(一)—— 链表

理论篇

链表是线性表的链式存储,它不需要使用地址连续的存储单元,而是通过指针建立数据元素之间的逻辑关系。

  1. 优点:插入、删除操作不需要移动元素,只需要修改指针;
  2. 缺点:不支持随机存取,不能直接找到表中某个特定的节点,需要从头开始遍历,依次查找;
类别 顺序表 链表
存取方式 顺序存取、随机存取 不支持随机存取
存储结构 逻辑相邻位置也相邻 逻辑相邻位置不一定相邻
查找 按序查找O(1) 按序查找O(n)
插入、删除 需要移动众多元素 只需修改指针O(1)
空间分配 预先分配足够大的空间 需要时分配

单链表

单链表:即线性表的链式存储,通过一组任意的存储单元来存储链表节点,每个节点包含数据域和后继指针域。

单链表的存储结构

python实现:

1
2
3
4
class ListNode(object):
def __init__(self,val):
self.val = val
self.next = None

头结点:在单链表第一个节点之前附加一个节点,称为头结点,头结点值域可以不设任何信息,也可记录表长等信息。头指针能够统一第一个位置和其他位置上的很多操作(特别是插入、删除),使得代码逻辑更加清晰。

单链表的基本操作

创建

可通过头插法和尾插法两种方式创建单链表:

  • 头插法:每次将新节点插入到第一个位置,链表节点顺序和原始输入顺序逆序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def create_link(nums):
"""
头插法创建单链表
"""
dummy = ListNode(0)
for num in nums:
node = ListNode(num)
dummy.next,node.next = node,dummy.next
return dummy.next

link = create_link([1,2,3])
while link:
print(link.val)
link = link.next
3
2
1
  • 尾插法:每次将新节点插入到链表尾部,与输入顺序相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def create_link(nums):
"""
尾插法创建单链表
"""
tail = dummy = ListNode(0)

for num in nums:
tail.next = tail = ListNode(num)
return dummy.next

link = create_link([1,2,3])
while link:
print(link.val)
link = link.next
1
2
3
查找
  • 按值查找:从前向后依次比较,找到则返回
1
2
3
4
5
6
7
8
def get_element_by_val(head,val):
"""
在链表head中查找值为val的第一个节点,找到该节点则返回,找不到则返回None
"""
p = head
while p and p.val != val:
p = p.next
return p
  • 按序号查找:查找第i个节点,链表计数时,注意初始对齐,即初始count的值对应初始节点,条件不满足时的coun的值对应最终节点;
1
2
3
4
5
6
7
8
9
10
11
12
def get_element_by_id(head,i):
"""
在链表head中查找第i个节点,并返回,未找到则返回None
"""
if i < 1:
return None
count = 1
p = head
while p and count < i:
p = p.next
count += 1
return p
遍历
  • 获取链表长度:遍历的同时统计计数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def get_length(head):
    """
    获取链表head的长度
    """
    p = head
    count = 0
    while p:
    p = p.next
    count += 1
    return count
  • 获取尾指针:根据尾指针的next域为None来查找
1
2
3
4
5
6
7
8
9
10
def get_tail(head):
"""
获取链表head的尾节点
"""
if not head:
return None
p = head
while p.next:
p = p.next
return p
插入
  • 在第i-1个节点之后插入:要插入节点,需要找到其对应的前驱节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def insert_node(head,i,val):
"""
在第i-1个节点之后插入新节点,并返回插入后的链表,如果插入位置不合法返回False
"""
p = dummy = ListNode(0)
dummy.next = head
if i < 1:
return False
count = 0
while p and count < i - 1:
p = p.next
count += 1
if not p:
return Fasle
else:
new_node = ListNode(val)
p.next,new_node.next = new_node,p.next
return dummy.next
  • 在第i个节点之前插入:如果无法获取其前驱节点,可通过换值实现插入
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def insert_node(head,i,val):
    """
    在第i个节点之前插入新节点
    """
    p = dummy = ListNode(0)
    dummy.next = head
    if i < 1:
    return False
    count = 0
    while p and count < i:
    p = p.next
    count += 1
    if not p:
    return Fasle
    else:
    new_node = ListNode(val)
    # 插入第i个节点之后,再换值
    p.next,new_node.next = new_node,p.next
    p.val,new_node.val = new_node.val,p.val
    return dummy.next
删除
  • 删除第i-1个节点的后继节点:同样的要删除一个节点需要先找到其对应的前驱节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def del_node(head,i):
    p = dummy = ListNode(0)
    dummy.next = head
    if i < 1:
    return False
    count = 0
    while p and count < i-1:
    p = p.next
    count += 1
    if p is None or p.next is None:
    return Fasle
    else:
    p.next = p.next.next
    return dummy.next
  • 删除第i个节点:如果无法找到前驱节点,可删除第i个节点的后继节点,然后再将第i个节点中的值替换为其后继节点中的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def del_node(head,i):
p = dummy = ListNode(0)
dummy.next = head
if i < 1:
return False
count = 0
while p and count < i:
p = p.next
count += 1
if p is None or p.next is None:
return Fasle
else:
val = p.next.val
p.next = p.next.next
p.val = val
return dummy.next

双链表

单链表无法直接获取前驱节点,需要从头重新遍历,时间复杂度为O(n),双链表通过引入前驱指针解决了这个问题。

双链表的存储结构

python实现:

1
2
3
4
5
class Doublelink(object):
def __init__(val):
self.val = val
self.prior = None
self.next = None

双链表的基本操作

双链表的查找和单链表基本一致,只不过多了一个反向查找的方向;双链表的插入和删除操作前后需要保持双链表的基本结构,加入需要在p节点后插入一个新节点node:

1
p.next.prior, node.next, p.next, node.prior = node,p.next.next, node, p

循环单链表

  • 循环单链表在单链表的基础上使得尾节点的next指针指向头结点,构成一个环;这样做的好处是可以在任意位置遍历整个链表。
  • 如果对单链表常做的操作是在表头和表尾,此时可使用带尾指针的循环链表;

循环双链表

  • 循环双链表是在双链表的基础上使得尾节点的next指向头结点,使头节点的prior指向尾节点;
### 静态链表 在不支持指针的高级语言中可以使用二元组数组来实现链表,每个节点用一个二元组(val,next_id)来表示,其中val是节点的数据域,next_id是节点的指针域,表示后继节点的下标,也叫游标。

实战篇

链表中常用技巧

  1. 绘图:链表操作常常涉及到很复杂的指针变换,建议先画出操作图示,按图示理清算法思路后再进行代码编写;
  2. 序列赋值:python的序列赋值给多个指针赋值带来了巨大便利,牢记序列赋值的两个关键点:
    1. 右侧生成元组:右侧多个对象会生成一个临时元组,指向这些变量所对应的原始对象,只要这些对象在赋值期间没有被原地修改,就能保持原始的值;
    2. 左侧依序赋值:依次将元组中的对象按左侧变量的顺序进行赋值;如果前面的赋值会改变后面的变量含义,则应将后面的变量放在前面先进行赋值;
  3. 头结点:引入头结点能够统一所有位置上的操作,简化代码逻辑;
  4. 分身哨兵:在移动指针时,如果后续还需要用到该位置的指针,可以复制一个分身哨兵代替原来的指针进行移动;
  5. 递归:链表的递归式结构决定了很多问题都可以通过递归的思路来求解;
  6. 快慢指针:通过快慢指针可以找到链表的(上/下)中位数、还可以判断链表是否有环、以及环的入口;
  7. 分类重组:如果需要将链表按照某种条件进行重排,可以将满足条件的单独作为一个链表,不满足条件的单独作为一个链表,最后再将它们拼接;

LeetCode经典题目

反转链表
  • 问题:反转单链表
  • 思路:三指针法,pre代表新链表头指针,head代表旧链表头指针,head.next代表旧链表头指针的下一个节点;head加入到pre,head移动到head.next,pre移动到head。
  • 代码:核心head.next,pre,head = pre,head,head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pre = None
while head:
# tmp = head
# head = head.next
# tmp.next = pre
# pre = tmp
head.next,pre,head = pre,head,head.next
return pre
反转链表II
  • 问题:反转从位置 m 到 n 的链表。请使用一趟扫描完成反转
  • 思路:找到m-1位置的节点作为pre_start,第m位置的节点start,第n位置节点end,第n+1位置节点end_next,对m-n范围内的链表进行逆转,再和其他段拼接
  • 代码:
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
26
27
28
29
30
class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
p = dummy = ListNode(0)
dummy.next = head

count = 0
while p:
if count == m-1:
start_pre = p
break
else:
p = p.next
count += 1

start = p = p.next
pre = None
while count < n:
p.next, pre, p = pre, p, p.next
count += 1
end = pre
end_next = p

start_pre.next, start.next = end, end_next
return dummy.next
合并两个有序链表
  • 问题:将两个有序链表合并为一个新的有序链表并返回,新链表是通过拼接给定的两个链表的所有节点组成的;
  • 思路:创建一个个新的头节点,比较两个链表的节点,依次将较小者插入到新链表尾部,直至某个链表为空,再将另一个链表连接至新链表末尾;
  • 代码:核心p.next = l1 or l2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
p = dummy = ListNode(0)

while l1 and l2:
if l1.val < l2.val:
p.next = p = l1
l1 = l1.next
else:
p.next = p = l2
l2 = l2.next
p.next = l1 or l2

return dummy.next
合并K个有序链表
  • 问题:合并 k 个排序链表,返回合并后的排序链表
  • 思路:使用二路归并排序算法
    • (1)先将k个链表划分为两组,递归地对这两组链表进行合并,如果某组链表只有一条就直接返回这条链表;
    • (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
26
27
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
n = len(lists)
if n == 0:
return None
elif n == 1:
return lists[0]

mid = (n-1)/2
l1 = self.mergeKLists(lists[:mid+1])
l2 = self.mergeKLists(lists[mid+1:])

p = dummy = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
p.next = p = l1
l1 = l1.next
else:
p.next = p = l2
l2 = l2.next

p.next = l1 or l2

return dummy.next
回文链表
  • 问题:判断一个链表是否为回文链表
  • 思路:找到中位数(下中位数)-前半部分逆序-对比前后部分,全相同才是回文链表
  • 代码:核心是寻找中位数
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
26
27
28
29
30
31
32
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
def get_mid(head):
# 获取上中位元素
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow

def reverse_link(head):
p,pre = head,None
while p:
p.next, pre, p = pre,p,p.next
return pre

if not head or not head.next:
return True
mid = get_mid(head)
re_mid = reverse_link(mid)

p,q = head,re_mid
while q:
if q.val != p.val:
return False
else:
p,q = p.next,q.next

return True
相交链表
  • 问题:找到两个单链表相交的起始节点
  • 思路:跑完自己跑对方,首遇非空即为交点,为空则无交点
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
pa = headA
pb = headB

while pa != pb:
pa = pa.next if pa else headB
pb = pb.next if pb else headA

return pa
环形链表
  • 问题:给定一个链表,判断链表中是否有环
  • 思路:快慢指针,快完之前相遇则有环,否则无环
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow = fast = head
while fast and fast.next:
slow,fast = slow.next,fast.next.next
if slow == fast:
return True
return False
环形链表II
  • 问题:给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
  • 思路:快慢指针-判断环,相遇说明有环,相遇后派一个新的慢指针从头开始移动,与原始慢指针的下次相遇点既是环的入口。证明,y = (n-m)c+x,其中x是第一次相遇点到入口的距离,y是起点到入口的距离。
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow1 = fast = head
while fast and fast.next:
slow1 = slow1.next
fast = fast.next.next
if slow1 == fast:
slow2 = head
break
else:
return None

while slow1 != slow2:
slow1 = slow1.next
slow2 = slow2.next
else:
return slow1
奇偶链表
  • 问题:给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
  • 思路:分类重组,使用两个哑结点,一个向后插入奇数结点,一个向后插入偶数结点,最后再将二者合并
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
tail1 = link1 = ListNode(0)
tail2 = link2 = ListNode(0)
count = 1
p = head

while p:
if count%2:
tail1.next = p
tail1 = tail1.next
else:
tail2.next = p
tail2 = tail2.next
p = p.next
count += 1
tail2.next = None
tail1.next = link2.next

return link1.next
两两交换链表中的节点
  • 问题:给定一个链表,两两交换其中相邻的节点,并返回交换后的链表,给定 1->2->3->4, 你应该返回 2->1->4->3
  • 思路:交换前两个,递归求出后面的,再连接
  • 代码:
1
2
3
4
5
6
7
8
9
10
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
p = head.next
p.next, head.next = head, self.swapPairs(p.next)
return p
k 个一组翻转链表
  • 问题:给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。给定这个链表:1->2->3->4->5,当 k = 3 时,应当返回: 3->2->1->4->5。
  • 思路:先统计链表长度n,总共有n/k份长度为k的需要逆序,循环逆序即可
  • 代码:
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
26
27
28
29
30
31
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head or k == 1:
return head

dummy = ListNode(0)
p = dummy.next = head
n = 0
while p:
p = p.next
n += 1
t = n/k

pre_start = dummy
p = head
for i in range(t):
count = 0
start = p
pre = None
while count < k:
count += 1
p.next,pre,p = pre,p,p.next
end = pre
start.next = p
pre_start.next = end
pre_start = start
return dummy.next
排序链表
  • 问题:对链表进行排序
  • 思路:可以用插入排序、快排或归并排序
    • 插入排序:使用两个指针,p.next代表当前待插入的元素,q.next代表已排序的节点,每次q.next从头开始遍历,直至找到第一个不小于p.next.val的节点,将其插入;
    • 快排:分类重组,将节点划分为小于less、等于eq、大于more某个值的三个链表->递归地快排less和more->合并三个链表;
    • 归并排序:寻找中位数-两侧归并排序(空或单节点直接返回)-合并两侧归并结果;
  • 代码:
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
# 插入排序
def insert_sort_link(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
q = dummy = ListNode(0)
p = dummy.next = head

while p.next:
while p.next.val > q.next.val:
q = q.next
if p == q:
p = p.next
else:
p.next.next, p.next, q.next = q.next, p.next.next, p.next
q = dummy
return dummy.next

# 快排
def quick_sort_link(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
def patition(head,val):
less = u = ListNode(0)
eq = v = ListNode(0)
more = w = ListNode(0)
while head:
if head.val < val:
u.next = u = head
elif head.val == val:
v.next = v = head
else:
w.next = w = head
head = head.next
u.next = v.next = w.next = None
return less,eq,more

def get_tail(head):
tail = head
if tail:
while tail.next:
tail = tail.next
return tail

def quick_sort(head):
if head:
less,eq,more = patition(head,head.val)
l1 = ListNode(0)
l1.next = quick_sort(less.next)
l2 = ListNode(0)
l2.next = quick_sort(more.next)
get_tail(l1).next = eq.next
get_tail(eq).next = l2.next
return l1.next
else:
return None

return quick_sort(head)

# 归并排序
def merge_sort_link(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
def get_mid(head):
"""
找到下中位数,head不为None
"""
slow,fast = head,head.next
while fast and fast.next:
slow,fast = slow.next,fast.next.next
return slow

def merge(l1,l2):
"""
归并两个有序链表
"""
dummy = p = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
if l1:p.next = l1
if l2:p.next = l2
return dummy.next

def merge_sort(head):
if not head:
return None
if not head.next:
return head
mid = get_mid(head)
# print mid.val
l1 = head
l2 = mid.next
mid.next = None

left = merge_sort(l1)
right = merge_sort(l2)
res = merge(left,right)

return res

return merge_sort(head)

两数相加
  • 问题:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
  • 思路:递归思路更简洁
    • 两个都有,随便用哪个节点放结果(l1,l2,flag),然后next指向子问题的解
      • 其中一个没有,只需要计算有的和flag的和,next指向子问题的解
      • 两个都没有且flag不为0,新建节点存储,否则返回None
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""

def add_all(flag,l1,l2):
if l1 is None and l2 is None:
return ListNode(flag) if flag else None
elif l1 is None or l2 is None:
if l1 is None:
l1,l2 = l2,l1
if flag:
flag, l1.val = divmod(l1.val + flag, 10)
l1.next = add_all(flag,l1.next,l2)
return l1
else:
flag,l1.val = divmod(l1.val+l2.val+flag,10)
l1.next = add_all(flag,l1.next,l2.next)
return l1
return add_all(0,l1,l2)
两数相加II
  • 问题:给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出: 7 -> 8 -> 0 -> 7
  • 思路:先逆序,再相加,转化为问题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
26
27
28
29
30
31
32
33
34
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
def reverse_link(head):
p, pre = head, None
count = 0
while p:
count += 1
p.next,pre,p = pre,p,p.next
return pre,count

l1_re,count_l1 = reverse_link(l1)
l2_re,count_l2 = reverse_link(l2)

if count_l1 < count_l2:
l1_re,l2_re,count_l1,count_l2 = l2_re,l1_re,count_l2,count_l1

head1 = l1_re
head2 = l2_re
flag = 0
while head1:
if head2:
flag,head1.val = divmod(head1.val + head2.val + flag,10)
head2 = head2.next
else:
flag,head1.val = divmod(head1.val + flag,10)
if head1.next is None and flag:
head1.next = ListNode(flag)
flag = 0
head1 = head1.next
return reverse_link(l1_re)[0]
旋转链表
  • 问题:给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数
  • 思路:等价于右移k%n,这相当于将最后k%n个节点插入到头结点后面,只需要找到第n-k%n个节点和尾节点(头结点-按序查找-插入)
  • 代码:
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
26
27
28
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head:
return head
dummy = ListNode(0)
p = dummy.next = head
n = 1
while p.next:
p = p.next
n += 1
tail = p

k = k % n
if k == 0:
return head

p = head
count = 1
while count < n - k:
p = p.next
count += 1
dummy.next, tail.next, p.next = p.next, head, None

return dummy.next
删除链表的倒数第N个节点
  • 问题:给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。给定一个链表: 1->2->3->4->5, 和 n = 2。当删除了倒数第二个节点后,链表变为 1->2->3->5。
  • 思路:先用一个指针p移动到第n+1个节点,然后安排另一个指针q从头节点开始移动,直至p==None,q指向了要删除节点的前一个节点。
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head

p = q = dummy
count = 0
while p:
p = p.next
if count >= n+1:
q = q.next
count += 1

q.next = q.next.next

return dummy.next
复制带随机指针的链表
  • 问题:给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝。
  • 思路:第一次遍历,先创建所有节点;第二次遍历,再建立节点间的连接;
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if not head:return None
dic = {}
p = head
while p:
dic[p] = RandomListNode(p.label)
p = p.next

p = head
while p:
dic[p].next = dic.get(p.next,None)
dic[p].random = dic.get(p.random,None)
p = p.next

return dic[head]
有序链表转换二叉搜索树
  • 问题:
  • 思路:中位数做根,递归地左链表作为左子树,右链表作为右子树
重排链表
  • 问题:给定一个单链表 L:L0→L1→…→Ln-1→Ln ,将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
  • 思路:找到中间位置的节点,将后半部分逆序,然后归并到前半部分
Split Linked List in Parts
  • 问题:Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.Input: root = [1, 2, 3], k = 5,Output: [[1],[2],[3],[],[]]
  • 思路:先得到每个链表的长度x,y = divmod(n,k) 分为k个链表,其中前y个长度为x+1,后面的长度为x;
Linked List Components
  • 问题:给定一个链表head和列表G,返回head中有多少个连续的块,块中节点的值在G中;Input: head: 0->1->2->3 G = [0, 1, 3] Output: 2
    Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components
  • 思路:在有哑元时只需要统计上一个节点不在G中当前节点在G中的个数;
删除排序链表中的重复元素 II
  • 问题:给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。输入: 1->2->3->3->4->4->5 输出: 1->2->5
  • 思路:pre代表可能重复的前一个节点,cur代表可能重复的第一个节点,pro代表与cur不同的第一个节点,统计pro和cur的距离,如果大于1则pre.next直接指向pro,cur移动至pro,重复统计,反之等于1,则pre,cur前进一步,直至cur为None
坚持原创技术分享,您的支持将鼓励我继续创作!