[数据结构与算法]JZ14 链表中倒数最后k个结点

描述

输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

快慢指针

又是一个不知道的知识点。

①边界条件：如果k比链表的长度还要大，则返回None。

②设置两个指针都指向头结点，但是fast?比?slow?快k步，slow比fast慢k步，fast到尾时，距离slow为k步，即尾距离slow为k步，得到此时slow为问题的解。

！！终于完整的实现了一遍链表的操作，感谢这位博主的博客https://blog.csdn.net/kuangd_1992/article/details/104127738?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~aggregatepage~first_rank_v2~rank_aggregation-8-104127738.pc_agg_rank_aggregation&utm_term=python%E5%A6%82%E4%BD%95%E8%BE%93%E5%85%A5%E9%93%BE%E8%A1%A8&spm=1000.2123.3001.4430

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


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

    def initList(self, data):
        # 创建头结点
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        # 逐个为 data 内的数据创建结点, 建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printlist(self, head):
        if head == None: return
        node = head
        while node != None:
            print(node.val, end=' ')
            node = node.next


class Solution:
    def FindKthToTail(self , pHead , k ):
        if k <= 0:
            return None
        count = 1
        slow = fast = pHead
        while fast != None:
            if count > k:
                slow = slow.next
            fast = fast.next
            count+=1
        if count <= k:
            return None
        return slow.val

if __name__ == '__main__':
    a = Solution()
    l = LinkList()
    data1 = [1, 2, 3, 4, 5]
    data2 = [2, 4, 6, 8, 10]
    l1 = l.initList(data1)
    l2 = l.initList(data2)
    l.printlist(l1)
    print("\r")
    l.printlist(l2)
    print("\r")
    m = a.FindKthToTail(l2.next, 3)
    print("m=", m)