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

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
    }

    // Delete header node 
    if lastN == list.Length() {
        // Delete chain header node 
        list.headNode = list.headNode.Next
        return
    }

    lowNode := list.headNode
    fastNode := list.headNode
    prevNode := list.headNode
    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 {
        // Delete chain header node 
        list.headNode = list.headNode.Next
    } 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) {
    if list1.HeadNode == nil && list2.HeadNode == nil {
        fmt.Println(" Both linked lists are empty ")
        return
    } else if list1.HeadNode == nil {
        list.HeadNode = list2.HeadNode
        return
    } else if list2.HeadNode == nil {
        list.HeadNode = list1.HeadNode
        return
    }

    curr1 := list1.HeadNode
    curr2 := list2.HeadNode
    if curr1.Data.(int) < curr2.Data.(int) {
        list.HeadNode = curr1
        curr1 = curr1.Next
    } else {
        list.HeadNode = curr2
        curr2 = curr2.Next
    }
    newHead := list.HeadNode
    currNew := newHead

    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{}
    if head1 == nil {
        return head2
    } else if head2 == nil {
        return head1
    } else {
        if head1.Data.(int) < head2.Data.(int) {
            newNode = head1
            newNode.Next = RecursionMergeList(head1.Next, head2)
        } else {
            newNode = head2
            newNode.Next = RecursionMergeList(head1, head2.Next)
        }
        return newNode
    }
}