题目:删除线性链表中数据域值为item的所有链结点
解题思路:先从链表的第2个链结点开始,从前往后依次判断链表中所有链结点是否满足条件,若某个链结点满足条件,则删除该链结点,否则不做删除操作。最后在回过头来判断链表中第1个链结点是否满足条件,若满足条件将其删除。
具体算法实现如下:
这里我们会用到toString(list))来打印一个线性链表出来。
这里我们会用到createLinklist(n)来建立一个线性链表出来
function deleteList(list, item) {
let p, q = list
p = list.link //p指向第2个结点
while ( p!=null ) {
if ( p.data == item ) {
q.link = p.link
p = null //释放空间
p = q.link
} else {
q = p
p = p.link
}
}
if ( list.data == item ) {
q = list
list = list.link
q = null //回收
}
return list
}
var list = createLinklist(10)
console.log('创建的list为:', toString(list))
var r_list = deleteList(list, 7)
console.log('删除item后的链表为:', toString(r_list))
性能:
时间复杂度为O(n)