数据结构题目19:删除线性链表中数据域值为item的所有链结点

题目:删除线性链表中数据域值为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)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
禁止转载,如需转载请通过简信或评论联系作者。