1.5寻找倒数第k个元素

寻找倒数第k个元素

方法一:

将单链表逆置,变换成寻找正数第k个元素

方法二:

快慢指针法,快指针比慢指针快k个节点,当快指针到达尾节点时,慢指针为倒数第k个节点

方法三:

顺序遍历两次链表法,第一次遍历求出链表长度n,将寻找倒数第k个元素转换成寻找正数第n-k个元素

代码实现方法二:

# -*-coding:utf-8-*- 
"""
@Author  : 图南
@Software: PyCharm
@Time    : 2019/9/5 18:03
"""
# 方法一:将单链表逆置,变换成寻找正数第k个元素
# 方法二:快慢指针法,快指针比慢指针快k个节点,当快指针到达尾节点时,慢指针为倒数第k个节点
# 方法三:顺序遍历两次链表法,第一次遍历求出链表长度n,将寻找倒数第k个元素转换成寻找正数第n-k个元素
# 本代码实现方法二
class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next


def con_link(n):
    head = Node()
    cur = head
    for i in range(1, n+1):
        node = Node(i)
        cur.next = node
        cur = node
    return head


def print_link(head):
    cur = head.next
    while cur:
        print(cur.data, end=' ')
        cur = cur.next
    print()


def getLastK(head, k):
    fast = head
    slow = head
    while k:
        fast = fast.next
        k -= 1
    while fast:
        fast = fast.next
        slow = slow.next
    return slow.data



if __name__ == '__main__':
    head = con_link(7)
    print_link(head)
    print(getLastK(head, 1))

运行截图:

###衍生内容:将单链表向右旋转k个节点 ####解题思路: 1. 首先找到链表倒数第k+l个结点slow和尾结点fast; 2. 把链表断开为两个子链表,其中,后半部分子链表结点的个数为k; 3. 使原链表的尾结点指向链表的第一个结点; 4. 使链表的头结点指向原链表倒数第k个结点。 ####代码实现: def rotateLink(head, k): fast = head slow = head while k: fast = fast.next k -= 1 while fast.next: fast = fast.next slow = slow.next fast.next = head.next head.next = slow.next slow.next = None return head ####运行截图:
原文地址:https://www.cnblogs.com/miao-study/p/11474926.html