链表中删除重复项
从链表中移除一个重复的值,链表是有序的。在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表 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。
- 递归调用当前节点的下一个节点的比较列表函数。