Leetcodeアルゴリズム系列(チェーンテーブル)の削除チェーンテーブル逆数N番目のノード

Leetcodeアルゴリズム系列(チェーンテーブル)の削除チェーンテーブル逆数N番目のノード
難易度:中程度に1つのチェーンテーブルを指定し、チェーンテーブルの最後からn番目のノードを削除し、チェーンテーブルのヘッダノードを返します.例:チェーンテーブルを1->2->3->4->5とn=2とする.最後から2番目のノードを削除すると、チェーンテーブルは1->2->3->5になります.説明:与えられたn保証は有効である.リンク:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
Python実現

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        """
           ：
        1.       head1=head
        2.      
                    head2
                   n   
                   n          ，        n ，       ，          
                head2  
             head2  n         ，      head    
                  head1
        """
        i = 0
        head1 = head
        while head:
            head2 = head
            j = 0
            while j < n + 1:
                if not head2:
                    return head1.next
                head2 = head2.next
                j += 1
            if not head2:
                head.next = head.next.next
                return head1
            i += 1
            head = head.next            

    def removeNthFromEnd2(self, head: ListNode, n: int) -> ListNode:
        """
            ，    
        """
        fast = head
        slow = head
        for i in range(n):
            fast = fast.next
        if not fast:
            #      N   
            return head.next

        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

    def removeNthFromEnd3(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        fast,slow = dummy,dummy
        for  i in range(n+1):
            fast = fast.next
        while fast is not None: 
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next


def create_listnode(list1: list) -> ListNode:
    print(list1)
    list1_nodes = [ListNode(x=node)  for node in list1]
    i = 0
    while i < len(list1) - 1:
        list1_nodes[i].next = list1_nodes[i + 1]
        i += 1

    return list1_nodes[0]


def print_lnode(lnode):
    while lnode:
        print(lnode.val)
        lnode = lnode.next

if __name__ == "__main__":
    l1 = create_listnode(list1=[1,2,3,4,5])
    solution = Solution()
    # head = solution.removeNthFromEnd(head=l1, n=1)
    head = solution.removeNthFromEnd2(head=l1, n=2)
    # if head.__class__ == ListNode:
    print_lnode(head)

Go言語実装

package main

import "fmt"

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

func (h *ListNode) Show() {
    fmt.Println(h.Val)
    for h.Next != nil {
        h = h.Next
        fmt.Println(h.Val)
    }
}

func removeNthFromEnd1(head *ListNode, n int) *ListNode {
    //              n   
    //       nil         n   
    // 0 ms 2.2 MB  Golang
    node := &ListNode{Next: head}
    fast, slow, step := node, node, 0
    for step < n {
        fast = fast.Next
        step++
    }
    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return node.Next
}

func removeNthFromEnd2(head *ListNode, n int) *ListNode {
    //         N   ，    
    //     “    n       。”    n     
    //  0 ms    2.2 MB  Golang
    var length int = n + 1
    var tempNodes []*ListNode = make([]*ListNode, length)
    var countNode int = 0
    var tail *ListNode = head
    for tail != nil {
        tempNodes[countNode%length] = tail
        tail = tail.Next
        countNode++
    }
    if countNode == n { //          
        return head.Next
    }
    if n == 1 { //         
        tempNodes[countNode%length].Next = nil
    } else { //      
        tempNodes[countNode%length].Next = tempNodes[(countNode+2)%length]
    }
    return head
}

func removeNthFromEnd3(head *ListNode, n int) *ListNode {
    //      
    // 0 ms 2.2 MB  Golang
    if head.Next == nil {
        return nil
    }
    node := &ListNode{Next: head}
    pointer, pointer2, length := node, node, 1
    for pointer.Next != nil {
        pointer = pointer.Next
        length++
    }
    index := length - n
    for i := 1; i <= length; i++ {
        if i == index {
            if pointer2.Next == nil {
                break
            }
            pointer2.Next = pointer2.Next.Next
            break
        } else {
            pointer2 = pointer2.Next
        }
    }
    return node.Next
}

func removeNthFromEnd4(head *ListNode, n int) *ListNode {
    //       0 ms   2.2 MB  Golang
    head, _ = handler(head, 1, n)
    return head
}

func handler(head *ListNode, layer, n int) (*ListNode, int) {
    if head == nil {
        return head, layer - 1
    }
    next, maxNum := handler(head.Next, layer+1, n)
    if layer == maxNum-n+1 {
        return head.Next, maxNum
    } else if layer == maxNum-n {
        head.Next = next
        return head, maxNum
    } else {
        return head, maxNum
    }
}

func create_link_list(list1 []int) *ListNode {
    head := &ListNode{Val: list1[0]}
    tail := head
    for i := 1; i < len(list1); i++ {
        tail.Next = &ListNode{Val: list1[i]}
        tail = tail.Next
        // head.Append(list1)
    }
    return head
}

func main() {
    l1 := []int{1, 2, 3, 4, 5}
    fmt.Println(l1)
    head1 := create_link_list(l1)
    head2 := removeNthFromEnd4(head1, 2)
    head2.Show()
}

 
実行結果
方法
実行時間
メモリ消費量
言語
python-遍歴判断
40 ms
13.9 MB
Python3
python-スナップポインタ、スライドウィンドウ
40 ms
13.8 MB
Python3
GO-スナップポインタ、スライドウィンドウ
0ms
2.2MB
Golang
Go-配列ストレージ、1回の遍歴
0ms
2.2MB
Golang
Go-2回遍歴
0ms
2.2MB
Golang
Go-再帰実装
0ms
2.2MB
Golang