七叶笔记 » golang编程 » 删除链表中的元素,但是只能使用一个指针

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

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

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  

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

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  

相关文章