Common linked list problems and their Go implementation

Remove duplicates from linked list

Remove a duplicate value from the linked list, the linked list is ordered.In a sorted linked list, there are duplicate nodes, please delete the duplicate nodes in the linked list, the duplicate nodes are not retained, and the pointer to the head of the linked list is returned.For example, the linked list 1->2->3->3->4->4->5 is processed as 1->2->5

Go language implementation is as follows:

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 } }}

Algorithm Analysis:

The algorithm uses only one layer of loops, the for loop is used to traverse the list.Whenever there is a node whose value is equal to the value of the next node, the current node next will point to the next of the next node.This will remove the next node from the list, the algorithm complexity is O(n)

List Reverse

Copy the contents of a linked list to another linked list in reverse order.If the original linked list contains elements in the order 1,2,3,4, the new linked list should contain elements in the order 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}

Traverse the list and add the node's value to a new list.Since the list is traversed forward and each node's value is added to the other list, the resulting list is the inverse of the given list.

Linked list comparison

Compares the values ​​of two linked lists for a given head pointer.

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) }}

• Lists are compared recursively.Also, if we reach the end of the list and both lists are empty.Then the two lists are equal, so return true

• Lists are compared recursively.This function will return false if any of the list is empty or if the corresponding node values ​​are not equal.

• Recursively calls the compare list function of the next node of the current node.