# Complete set of linked list operations of data structure and algorithm series (3) (go)

2020-11-09 10:50:13 The complete code below , And test code can be obtained from here github

#### Delete the one-way list from the bottom n Nodes

##### Method 1 ： Fast and slow pointer method
###### Ideas

Delete the last N Nodes , Suppose you look at it in reverse , To delete the N Nodes . that , A pointing head node （ The head node is also a data node ） The pointer moves forward N-1 After nodes , That's the point N Nodes

Now let's take a look at deleting the last one N Nodes , Suppose there are two pointers （ Quick pointer fastPtr、 Slow pointer lowPtr） All points to the head node , Quick pointer fastPtr Traverse backward N-1 After nodes , Slow pointer and fast pointer start traversing backward together , When the fast pointer reaches the last node , Where the slow pointer points , It's the last N The location of the nodes ###### Code implementation
``````func (list *List) DelLastNNode1(lastN int) {
if lastN > list.Length() || lastN <= 0 {
fmt.Println(" The position of the node to be deleted is illegal ")
return
}

// Delete tail node
if lastN == 1 {
list.RemoveLastNode()
return
}

if lastN == list.Length() {
return
}

fastStep := lastN-1
for fastNode.Next != nil {
if fastStep > 0 {
fastNode = fastNode.Next
fastStep--
continue
}
fastNode = fastNode.Next
prevNode = lowNode
lowNode = lowNode.Next
}
prevNode.Next = lowNode.Next
}``````
##### Method 2 ： The relationship between node position and node number
###### Ideas

I don't know how to delete the last one N Nodes , Just try to find out which one it is . therefore , The key is through the length of the list and N To find the bottom of N Which node is a positive number , It can be seen from observation that , Last but not least N A node is a positive number length-N+1 Nodes ,length Is the length of the list

###### Code implementation
``````func (list *List) DelLastNNode2(lastN int) {
if lastN > list.Length() || lastN <= 0{
fmt.Println(" The position of the node to be deleted is illegal ")
return
}

length := list.Length()
position := length-lastN+1

if position == 1 {
} else if position == length {
// Delete the end node of the linked list
list.RemoveLastNode()
} else {
// Delete the node at the specified position in the linked list
list.RemovePosition(position)
}
}``````

explain ： Delete single chain header node 、 Caudal node 、 Node implementation at the specified location , You can refer to my This article , Or here

``https://github.com/Rain-Life/data-struct-by-go``

#### Merge two ordered single linked lists

So is the question LeetCode Upper part 21 topic

##### Method 1 ： Conventional methods
###### Ideas

The conventional idea is , Create a new list , Then traverse the two linked lists to be merged , Compare the size of the two node values traversed , Suppose you want to merge the linked list in descending order , The node with smaller value is inserted into the new linked list , And the value of the small node backward traversal a bit , The node with higher value remains unchanged , Then continue to compare , Repeat the above steps , Pictured ( Be careful ： To show the process , The following figure does not consider whether the linked list is empty ) ###### Code implementation
``````func (list *List) MergeLinkedList(list1 List, list2 List) {
fmt.Println(" Both linked lists are empty ")
return
} else if list1.HeadNode == nil {
return
} else if list2.HeadNode == nil {
return
}

if curr1.Data.(int) < curr2.Data.(int) {
curr1 = curr1.Next
} else {
curr2 = curr2.Next
}

for curr1 != nil && curr2 != nil {
if curr1.Data.(int) < curr2.Data.(int) {
currNew.Next = curr1
curr1 = curr1.Next
} else {
currNew.Next = curr2
curr2 = curr2.Next
}
currNew = currNew.Next
}

if curr1 == nil {
currNew.Next = curr2
}
if curr2 == nil {
currNew.Next = curr1
}
}``````
##### Method 2 ： recursive
###### Ideas

The above conventional solution is realized by recursion , It's mainly the termination condition of recursion

###### Code implementation
``````func RecursionMergeList(head1 *Node, head2 *Node) *Node {
newNode := &Node{}
} else if head2 == nil {
} else {
} else {