LeetCode 61. 旋转链表-Python-快慢指针
原题链接
简单
作者:
shiqumi
,
2020-02-18 22:26:50
,
所有人可见
,
阅读 617
思路:
1、先求链表长度n, 把移动个数k模n,即k %= n, 因为翻转n次相当于不变,n为链表节点数
2、同删除倒数第k个节点的步骤:
- 创建快慢指针,让快指针先走k步,然后快慢指针每次同时走一步,当快指针走到尾节点时,停止
3、此时慢指针指向倒数第k+1个节点, 快指针指向尾节点
接下来是三板斧:
- 让原尾节点的下一个节点指向原头节点
- 让慢指针的下一个节点作为新的头节点(即倒数第k个节点作为新头节点)
- 最后让慢指针下一个界节点指向空节点(即倒数第k+1个节点作为新尾节点)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head:
return None
# 1、求链表长度
n = 0
p = head
while p:
n += 1
p = p.next
k %= n # k模n
# 2、快慢指针
first = head; second = head
while k:
first = first.next
k -= 1
while first.next:
first = first.next
second = second.next
# 3、指针操作
first.next = head
head = second.next
second.next = None # 空节点用None,而不是NULL
return head