常见链表题及其 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 循环用于遍历列表。 每当有一个节点的值等于下一个节点的值时，该当前节点下一个将指向下一个节点的下一个。 这将从列表中删除下一个节点，算法复杂度为 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。

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