递归地查找单链表倒数第k个元素-Python

Question

我是Python的新手，在学习Python的过程中练习简单的数据结构。我尝试使用递归实现在Python中查找倒数第k个元素的问题：

这是我的代码：

def kthtoLast(self,head,k,i):  #recursion
    if(head==None):
        return 0

    i= kthtoLast(self,head.next,k) + 1
    if(i==k):
        print(head.node)
    return i

但是我遇到了一个错误-

NameError: name 'kthtoLast' is not defined.

尽管我已经定义了函数并在创建类对象后调用它 -

l=LinkedList()
l.kthtoLast(l.head,3,0)

请问有人能够帮助我理解我哪里出错了吗？

完整的代码如下：

class Node(object):
    def __init__(self,node,next=None):
        self.node=node
        self.next=next
class LinkedList(object):
    def __init__(self,head=None):
        self.head=head
    def append(self,data):
        new_node=Node(data,self.head)
        self.head=new_node
    def kLast(self,current,k):  #recursion
        if(current.next==None):
            return 0
        i= kLast(self,current.next,k) + 1
        if(i==k):
            print(current.node)
        return i
l=LinkedList()
l.append(12)
l.append(45)
l.append(7988)
l.append(89)
l.append(74)
print(l.head)
l.kLast(l.head,3)

- ayushi agarwal

Answer 1

作为另一种选择，您可以使用两个指针的解决方案，这在复杂度方面更加高效。

以下是它的工作原理：

该解决方案有两个指针...（快指针和慢指针）。我们首先增加/移动快指针（而不移动/增加慢指针）。这样，快指针将按照n次计数移到下一个节点，然后我们也移动/增加慢指针。一旦快指针到达末尾，那么我们就知道慢指针在倒数第n个节点上。

一些额外信息： 倒数第二个表示下一个节点，倒数第1个表示最后一个节点本身！

               pointer
               to next
  +----------+ node     +----------+          +----------+
  | Data  |  +--------> | Data  |  +--------> | Data  |  |
  +----------+          +----------+          +----------+

     ^                                            ^
     |                                            |
     |                                            |
  +-------+                                    +-------+
  |slow   |                                    |fast   |
  |pointer|                                    |pointer|
  +-------+                                    +-------+
  keep moving the fast pointer to the end

  +------------------------------------------------------>

  but only move the slow pointer forward when fast pointer has passed n nodes

  +------->

这是代码：

class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = None

class LinkedList:  
    def __init__(self): 
        self.head = None

    def append(self, value):
        if not self.head:
            self.head = Node(value)
        else:
            temp = self.head
            # go to the last one 
            while temp.next:
                temp = temp.next
            # now we are just adding a new to the end of the linkedlist    
            temp.next = Node(value)

    # the main logic
    def print_nth_from_last(self, n): 
        slow_pointer = self.head 
        fast_pointer = self.head  


        counter = 1
        while(fast_pointer  is not None): 
            fast_pointer  = fast_pointer.next 
            # don't allow slower pointer to go to next node until the faster pointer has moved by nth value. 
            # in other words, hold slower_point behind nth value! 
            if counter > n: 
                slow_pointer = slow_pointer.next 
            counter +=1
        if n >= counter:
            print("error - nth value is greater than number of nodes you have ")
        else:   
            print (n,"elements from last is:" , slow_pointer.data)


#let's populate the linkedlist
linkedList = LinkedList() 
linkedList.append(20)
linkedList.append(4)
linkedList.append(15)
linkedList.append(35)

#note you can pass zero 
linkedList.print_nth_from_last(3) 

- grepit

Answer 2

当您从同一类的另一个实例方法调用类的实例方法时，应使用 self.<method>()，因此在您的情况下，调用变为 -

i = self.kthtoLast(head.next,k) + 1

- Anand S Kumar

Answer 3

假设你有一个ListNode：

class ListNode:
def __init__(self, data=0, next=None):
    self.data = data
    self.next = next

你可以这样做：

def find_n_to_last(node, n):
    """Returns nth to last element from the linked list."""
    def find_n_to_last_helper(node, n, count):
        if not node:
            return None

        result = find_n_to_last_helper(node.next, n, count)
        if count[0] == n:
            result = node.data

        count[0] += 1 
        return result 

    count = [0]
    return find_n_to_last_helper(node, n, count)

- Stan Bashtavenko