删除链表中的元素,但是只能使用一个指针

NothingLeft了 · · 101 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

先用使用常规方法,两个指针:

golang实现:

type Node struct {
    value int
    next  *Node
}

type Link struct {
    head  *Node
    tail  *Node
    lenth int
}

// 向链表中添加元素
func (link *Link) add(v int) {
    if link.lenth == 0 { // 当前链表是空链表
        link.head = &Node{v, nil}
        link.tail = link.head
        link.lenth = 1
    } else {
        newNond := &Node{v, nil}
        link.tail.next = newNond
        link.tail = newNond
        link.lenth += 1
    }
}

// 删除链表中的元素(双指针)
func (link *Link) remove(v int) {
    if link.lenth == 0 {
        fmt.Println("空链表,不支持该操作")
        return
    }
    var previous *Node = nil
    for current := link.head; current != nil; current = current.next {
        if current.value == v {
            if current == link.head { // 要删除的是头节点
                link.head = current.next
            } else if current == link.tail { // 要删除的是尾节点
                previous.next = nil
                link.tail = previous
            } else { // 要删除的是中间的节点
                previous.next = current.next
            }
            link.lenth -= 1
            break
        }
        previous = current
    }
}

// 打印链表
func (link *Link) printList() {
    if link.lenth == 0 {
        fmt.Println("空链表")
        return
    }
    for cur := link.head; cur != nil; cur = cur.next {
        fmt.Printf("%d ", cur.value)
    }
    fmt.Println()
}


python实现:

class Node:
    def __init__(self, value, next):
        self.value = value
        self.next = next

    def __str__(self):
        return str(self.value)

class Link:
    def __init__(self):
        self.head = None
        self.tail = None
        self.lenth = 0

    # 向链表中添加元素
    def add(self, v):
        if self.lenth == 0:  # 当前链表是空链表
            self.head = Node(v, None)
            self.tail = self.head
            self.lenth = 1
        else:
            new_node = Node(v, None)
            self.tail.next = new_node
            self.tail = new_node
            self.lenth += 1

    # 打印链表
    def print(self):
        if self.lenth == 0:
            print('空链表')
            return
        cur = self.head
        while True:
            if cur == None:
                print()
                break
            print(cur, end=' ')
            cur = cur.next

    # 删除链表中的元素
    def remove(self, v):
        if self.lenth == 0:
            return
        cur = self.head
        pre = None
        while True:
            if cur.value == v:
                if cur == self.head:  # 要删除的是头节点
                    self.head = cur.next
                elif cur == self.tail:  # 要删除的是尾节点
                    pre.next = None
                    self.tail = pre
                else:  # 要删除的是中间的节点
                    pre.next = cur.next
                self.lenth -= 1
                break
            pre = cur
            cur = cur.next
            if cur == None:
                print("未找到", v)
                break

只使用使用一个指针实现链表的删除:

使用一个指针删除链表示意图.jpg

golang实现:

func (link *Link) remove_with_one_pointer(v int) {
    if link.lenth == 0 {
        return
    }
    if link.tail.value == v { // 要删除的节点是尾节点,需特殊处理
        if link.lenth == 1 { // 如果链表只有一个节点
            link.head = nil
            link.tail = nil
        } else { //大于一个节点
            cur := link.head
            for ; cur.next.next != nil; cur = cur.next {
            } //找到尾节点的前一个节点
            cur.next = nil
            link.tail = cur
        }
        link.lenth -= 1
        return
    }
    //要删除的节点在头部/中间 的常规情况
    for cur := link.head; cur != nil; cur = cur.next {
        if cur.value == v {
            cur.value = cur.next.value
            cur.next = cur.next.next
            link.lenth -= 1
            return
        }
    }
    fmt.Println("未找到", v)
}

python实现:

def remove_with_one_pointer(self, v):
    if self.lenth == 0:
        return
    if self.tail.value == v:  # 要删除的节点是尾节点,需特殊处理
        if self.lenth == 1:  # 如果链表只有一个节点
            self.head = None
            self.tail = None
        else:  # 大于一个节点
            cur = self.head
            while True:
                if cur.next.next is None:  # 找到尾节点的前一个节点
                    break
                else:
                    cur = cur.next
            cur.next = None
            self.tail = cur
        self.lenth -= 1
        return
    # 要删除的节点在头部/中间 的常规情况
    cur = self.head
    while True:
        if cur.value == v:
            cur.value = cur.next.value
            cur.next = cur.next.next
            self.lenth -= 1
            break
        cur = cur.next
        if cur is None:
            print('未找到', v)
            break

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:NothingLeft了

查看原文:删除链表中的元素,但是只能使用一个指针

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

101 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传