剑指 倒数k个结点

k 与 n-k 的关系，当first走了k个节点，剩下就是n-k个，通过这个来计数，同时注意链表小于k长度的问题。

class Solution:
    def FindKthToTail(self , pHead , k ):
        # write code here
        first=last=pHead
        for i in range(k):
            if first==None:
                return None
            first=first.next
        while first!=None:
            first=first.next
            last=last.next
        return last

这个问题延申 删除倒数第K个节点 leetcode 19
核心是希望first节点比second节点可以超前n个节点。
要保证first 比 second 前n个节点，思考一下当first到None,second 与 first 差几个节点可以保证 second.next=second.next.next,可以保证删除倒数第k个节点，结果是相差n个。当然如果判断first的下一个为None时停止，则需要相差n-1个。
这里还需要注意一点是second 节点从头节点开始还是从头节点前一个开始。
如果从头节点前一个开始可以直接使用second=result=Node(0,head),而且最后返回result即可，而且head有可能是被删掉的节点。
然后特例包括
空链表
k>链表长度
k为最后一个
k=0

链表注意是谁的指针，需要返回哪一个。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

        if not head:
            return None
        if n==0:
            return head

        first=head
        second=result=ListNode(0,head)

        for i in range(n):
            if first==None:
                return None
            first=first.next

        while first!=None:
            second=second.next
            first=first.next

        second.next=second.next.next

        return result.next

def delete_k(head,k):

    if not head:
        return None

    result=Node(0,head)
    r=head
    l = head
    count=0

    while  l!=None and count<=k :
        l=l.next
        count+=1

    if l==None:
        return None

    while l!=None:

        r=r.next
        l=l.next

    r.next=r.next.next
    return result.next

以及在这里复习一下，构建单链表，尾插法（self.tail）与头插法的写法。

class Node():
    def __init__(self,val,next=None):
        self.val=val
        self.next=next
class singlelist():
    def __init__(self):
        self.head=None
        self.tail=None
    def add(self,val):
        node=Node(val)
        node.next=self.head
        self.head=node
    def append(self,data):
        if self.head==None:
            self.head=Node(data)
            self.tail=self.head
        else:
            self.tail.next=Node(data)
            self.tail=self.tail.next

使用栈

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

        if not head:
            return None
        if n==0:
            return head
        stack=[]
        l=result=ListNode(0,head)
        while result!=None:
            stack.append(result)
            result=result.next
        for i in range(n):
            cur=stack.pop()

        stack[-1].next=cur.next

        return l.next