常见链表题及其 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。

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