写点什么

常见链表题及其 Go 实现

作者:宇宙之一粟
  • 2022 年 7 月 16 日
  • 本文字数:899 字

    阅读完需:约 3 分钟

常见链表题及其 Go 实现

链表中删除重复项


从链表中移除一个重复的值,链表是有序的。在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表 1->2->3->3->4->4->5 处理后为 1->2->5


Go 语言实现如下:

func(list *List) RemoveDuplicate() {  curr := list.head  for curr != nil {    if curr.next != nil && curr.value == curr.next.value {      curr.next = curr.next.next    } else {      curr = curr.next    }   }}
复制代码


算法分析:

该算法只用了一层循环,for 循环用于遍历列表。 每当有一个节点的值等于下一个节点的值时,该当前节点下一个将指向下一个节点的下一个。 这将从列表中删除下一个节点,算法复杂度为

链表反转


将链表的内容以相反的顺序复制到另一个链表中。 如果原始链表包含顺序为 1,2,3,4 的元素,则新链表应包含顺序为 4,3,2,1 的元素。


func(list *List) CopyListReversed() *List {  var tempNode, tempNode2 * Node  curr := list.head  for curr != nil {    tempNode2 = &Node{curr.value, tempNode}    curr = curr.next    tempNode = tempNode2  }    ll2 := new(List)  ll2.head = tempNode  return ll2}
复制代码


遍历列表并将节点的值添加到新列表中。 由于列表是正向遍历的,并且每个节点的值都被添加到另一个列表中,所以形成的列表与给定列表相反.


链表对比

比较给定头指针的两个链表的值。

func (list *List) CompareList(ll *List) bool {  return list.compareListUtil(list.head, ll.head)}
func(list *List) compareListUtil(head1 *Node, head2 *Node) bool { if head1 == nil && head2 == nil { return true } else if (head1 == nil) || (head2 == nil) || (head1.value != head2.value) { return false } else { return list.compareListUtil(head1.next, head2.next) }}
复制代码
  • 列表是递归比较的。 此外,如果我们到达列表的末尾并且两个列表都是空的。 然后两个列表相等,因此返回 true

  • 列表是递归比较的。 如果列表中的任何一个为空或对应节点的值不相等,则此函数将返回 false。

  • 递归调用当前节点的下一个节点的比较列表函数。

用户头像

宇宙古今无有穷期,一生不过须臾,当思奋争 2020.05.07 加入

🏆InfoQ写作平台-第二季签约作者 🏆 混迹于江湖,江湖却没有我的影子 热爱技术,专注于后端全栈,轻易不换岗 拒绝内卷,工作于软件工程师,弹性不加班 热衷分享,执着于阅读写作,佛系不水文

评论

发布
暂无评论
常见链表题及其 Go 实现_链表_宇宙之一粟_InfoQ写作社区