2019-06-10剑指 链表中的第k个节点

15min 关键在边界条件。k=len+1的时候

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        n=0
        dead=ListNode(None)
        dead.next=head
        fast=dead
        slow=dead
        try:
            while n<k:
                n+=1
                fast=fast.next
            if fast==None:return None  #这里不容易注意到
            while fast!=None:
                fast=fast.next
                slow=slow.next
            return slow
        except Exception as e:
            return None

不使用try catch

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        n=0
        dead=ListNode(None)
        dead.next=head
        fast=dead
        slow=dead
        while n<k:
            n+=1
            if fast!=None:fast=fast.next
            if fast==None:return None # 不仅仅是当下为None，上一步走一步为none
        while fast!=None:
            fast=fast.next
            slow=slow.next
        return slow

不使用哑结点还是有点难想的，特别是边界条件，其中i与k的判断条件

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        fast=head
        slow=head
        i=1
        while fast!=None:
            if i>k:slow=slow.next
            fast=fast.next
            i+=1
        return slow if i>k else None

使用哑结点比较好理解

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        dead=ListNode(None)
        dead.next=head
        f=dead
        s=dead
        i=0
        while f!=None:
            if i>=k:s=s.next
            f=f.next
            i+=1
        return s if i>k else None

最容易错的点在于例如len5 6