直通BAT面试算法精讲--链表(1)
链表问题知识点和注意事项
1.链表问题算法难度不高,但考察代码实现能力。
2.链表和数组都是一种线性结构,数组是一段连续的存储空间,链表空间不一定保证连续,是临时分配的
链表的分类
1.按链接方向分类:单链表,双聊表
2.有无环:普通链表,循环链表
链表问题代码实现关键点
1.链表调整函数的返回值,类型要求往往是节点类型。
2.处理链表过程中,先采用画图的方式理清逻辑。
3.链表问题对于边界条件讨论要求严格。
关于链表插入和删除的注意事项
1.特殊处理链表为空,或者链表长度为1的情况。
2.注意插入操作的调整过程(需要找前后节点)
3.注意删除操作的调整过程(需要找前后节点)
注意:头尾节点及空节点需要特殊考虑。
双链表的插入与删除和单链表类似,但是需额外考虑previous指针的指向。
单链表的反转操作
1、当链表为空或长度为1,特殊处理。
2.对一般情况,如下
已经反转好的头部为head,当前节点now。
案例一
环形链表插值练习题
题干:
给定链表的信息,结点值的数组arr,下一个结点值的位置的数组nxt,和要插入的值num,要保证插入后这个环形单链表依然有序
要求时间复杂度为O(n),空间复杂度为O(1)
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkList:
def __init__(self):
self.head = None
def insert(self,arr,nxt,num):
node = Node(num)
if not arr:
return node
#将数组arr中的元素创建结点连接到temp上去
for i in range(len(arr)):
newNode = Node(arr[nxt[i]])
if not self.head:
self.head = newNode
first = self.head
else:
self.head.next = newNode
self.head = newNode
#如果插入的num是最小值,则插入链表的最前
if num < first.data:
self.head.next = node
node.next = first
return node
#插入两个值之间
p = first
q = p.next
while q:
if p.data<=num and num<=q.data:
p.next = node
node.next = q
break
p = q
q = q.next
#若q为null,表示num是最大值,则插入最后一个节点后
q.next = node
node.next = first
return first
总觉得这个有点毛病。。。。
案例二
访问单个节点的删除练习题
题干:
给定一个链表中的结点node,但不给定整个链表的头结点。如何在链表中删除node?
请实现这个函数,要求时间复杂度为O(1)
解答:
典型的“狸猫换太子”, 若要删除该节点,正常情况下,应该要知道该节点的前面节点的指针,但是由于单链表中没有头结点,所以无法追溯到该节点前面的那个节点,因此,这里采用了“移花接木”的方法。设该节点为B,下一个节点为C。那么,首先将B节点的内容替换为C节点的内容,然后,将C节点删除,这样就达到了我们的目的。
但是这样存在一个问题,就是如果给定的该节点是最后一个节点,将无法采取这种方法!
这种删除方式并不是删除了该删除的结点,而是进行了值的拷贝,实际工程中不可取
如果能限制条件说,给定的node节点不是最后一个节点,那么删除代码如下所示:
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkList:
def __init__(self,node):
p = node.next
if p == None:
node = None
else:
node.next = p.next
node.data = p.data
del p
上一篇: 鬼片里面的基本定律
下一篇: 高频面试算法题——链表
推荐阅读