常见链表题及其 Go 实现

2022 年 7 月 16 日
本文字数：899 字
阅读完需：约 3 分钟

链表中删除重复项

从链表中移除一个重复的值，链表是有序的。在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表 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 循环用于遍历列表。每当有一个节点的值等于下一个节点的值时，该当前节点下一个将指向下一个节点的下一个。这将从列表中删除下一个节点，算法复杂度为 $O (n)$

链表反转

将链表的内容以相反的顺序复制到另一个链表中。如果原始链表包含顺序为 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。
递归调用当前节点的下一个节点的比较列表函数。

发布于: 刚刚阅读数: 4

宇宙之一粟

关注

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

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

发布

暂无评论

创作场景

常见链表题及其 Go 实现

链表中删除重复项

链表反转

链表对比

宇宙之一粟

评论