剑指offer 链表中倒数第k个结点

Posted on |

题目

类似于Leetcode 19. 删除链表的倒数第N个节点

方法

进阶思路：设置2个指针，第一个指针走K步之后，第二个指针开始从头走，这样两个指针之间始终相隔K，当指针2走到链表结尾时，指针1的位置即倒数K个节点
思路推广：寻找中间节点, 两个指针一起, 第一个指针每次走两步, 第二个指针每次走一步, 快指针指到尾部, 慢指针正好指到中间

边界条件比较多：

  • head为空，k无效
  • k比链表长度大

优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if not head or k<=0:
            return None

        slow=fast=head
        for i in range(k-1):
            if fast.next is None:
                return None
            fast=fast.next
        while fast.next:
            fast=fast.next
            slow=slow.next
        return slow

建议采用哑节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if not head or not k:
            return
        dummy=ListNode(0)
        dummy.next=head
        fast,slow=dummy,dummy

        for i in range(k):
            if fast.next is None:
                return None
            fast=fast.next
        while fast:
            fast=fast.next
            slow=slow.next
        return slow