当前位置：网站首页>Common linked list questions and their go implementation

Common linked list questions and their go implementation

2022-07-19 01:02:00 【InfoQ】

Delete duplicates in the linked list

Remove a duplicate value from the linked list , The linked list is ordered . In a sorted list , There are duplicate nodes , Please delete the duplicate nodes in the list , Duplicate nodes are not reserved , Return chain header pointer . for example , Linked list 1->2->3->3->4->4->5 After treatment: 1->2->5

Go The 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 loop ,for Loop is used to traverse the list . Whenever the value of one node equals the value of the next node , The next node of the current node will point to the next node . This will remove the next node from the list , The algorithm complexity is

List reversal

Copy the contents of the linked list to another linked list in reverse order . If the original linked list contains 1,2,3,4 The elements of , Then the new linked list should contain 4,3,2,1 The elements of .

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 value of the node to the new list . Because the list is forward traversal , And the value of each node is added to another list , So the formed list is opposite to the given list .

Linked list comparison

Compare the values of two linked lists with a given header 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 recursively compared . Besides , If we reach the end of the list and both lists are empty . Then the two lists are equal , Therefore return true