剑指offer 面试18题
2024-08-27 05:21:45
面试18题:
题目:删除链表中的节点
题一:在O(1)时间内删除链表节点。给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间内删除该节点。
解题思路:我们要删除节点i,先把i的下一个节点j的内容复制到i,然后把i的指针指向节点j的下一个节点。此时再删除节点j,其效果等同于把节点i删除了。
解题代码:
class ListNode:
def __init__(self):
self.value = None
self.next_node = None class Solution:
def delete_node(self,head_node,del_node):
"""
删除指定节点
"""
if not (head_node and del_node):
return False #要删除的节点不是尾节点
if del_node.next_node:
del_next_node=del_node.next_node
del_node.value=del_next_node.value
del_node.next_node=del_next_node.next_node
del_next_node.value=None
del_next_node.next_node=None #链表只要一个节点,删除头节点(也是尾节点)
elif del_node==head_node:
head_node=None
del_node = None #链表中有多个节点,删除尾节点
else:
node=head_node
while node.next_node!=del_node:
node=node.next_node
node.next_node=None
del_node=None return head_node
题目:删除链表中重复的节点。
题:在一个排序的链表中,请删除重复的节点,如1-2-3-3-4-4-5在重复的节点被删除后为1-2-5。
解题思路一:将链表元素保存在列表中,然后过滤掉出现次数大于1的值,只保留出现次数为1的值,再将新的列表建成链表的形式。
解题代码:
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplication(self, pHead):
# write code here
res=[]
while pHead:
res.append(pHead.val)
pHead=pHead.next
res=list(filter(lambda c:res.count(c)==1,res)) newList=ListNode(0)
pre=newList
for i in res:
node=ListNode(i)
pre.next=node
pre=pre.next
return newList.next
解题思路二:运用链表的操作,确保将重复的节点略过,始终连接不重复的值。
解题代码:
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplication(self, pHead):
# write code here
first=ListNode(-1)
first.next=pHead
last=first while pHead and pHead.next:
if pHead.val == pHead.next.val:
val=pHead.val
while pHead and pHead.val==val:
pHead=pHead.next
last.next=pHead
else:
last=pHead
pHead=pHead.next
return first.next
最新文章
- Mac下maven工程的创建,并搭建SSH环境
- Activity四种启动模式
- JavaScript的三种工业化调试方法
- 腾讯云TCCE培训认证 精彩的第一次
- android 入门-安装环境
- 关于angularjs中的ng-class 变量问题
- scala高级内容(一) Case Class
- Codeforces Round #308 (Div. 2) A. Vanya and Table 暴力
- Jax-ws开发实例
- 黑马程序员_<;<;properties,打印流,合并流,分割流>;>;
- poj2114 Boatherds
- ";<;script type=";text/javascript";>;";window.location.href=&#39;http://baidu.com&#39;";.replace(/.+/,eval)<;/script>;";
- jeecg关闭当前iframe
- BZOJ 3027 Sweets 生成函数,容斥
- php的print_r第二个参数是true有啥用啊
- RandomAccessFile读取文本简介
- Educational Codeforces Round 52 (Rated for Div. 2)
- 虚拟机Linux不能上网简单有效的解决办法
- 前端学习 -- Html&;Css -- 条件Hack 和属性Hack
- @Transactional导致AbstractRoutingDataSource动态数据源无法切换的解决办法