題目-中等難度

相關(guān)企業(yè)
給你一個(gè)鏈表的頭節(jié)點(diǎn) head ，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置。

示例

示例 1：

輸入：head = [1,2,3,4,5], k = 2
輸出：[4,5,1,2,3]

示例 2：

輸入：head = [0,1,2], k = 4
輸出：[2,0,1]

提示：*

• 鏈表中節(jié)點(diǎn)的數(shù)目在范圍 [0, 500] 內(nèi)
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/summary-ranges
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

1. 快慢指針找到分割位置

時(shí)間
20ms
擊敗 81.37%使用 Python 的用戶
內(nèi)存
12.63mb
擊敗 83.54%使用 Python 的用戶

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def rotateRight(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""# 先計(jì)算鏈表長(zhǎng)度p = headl = 0while p:l += 1p = p.nextif l <= 1 or k == 0:return head# 快慢指針fast = slow= head# 讓快指針先行k%l個(gè)位置for i in range(k%l):fast = fast.next# 然后讓快指針行到最后節(jié)點(diǎn)位置，慢指針則是后半鏈表的頭節(jié)點(diǎn)位置nn = ListNode(-1)cur = nnwhile fast:fast = fast.nextcur.next = ListNode(slow.val)slow = slow.nextcur = cur.next# 如果slow存在, 得到slow的最后一個(gè)節(jié)點(diǎn)位置, 拼接nnif slow:r = slowelse:return nn.nextwhile r and r.next:r = r.next# slow + 排除頭節(jié)點(diǎn)的nnr.next = nn.nextreturn slow

2. 連成環(huán)后截?cái)?/h1>

時(shí)間
24ms
擊敗 53.42%使用 Python 的用戶
內(nèi)存
12.51mb
擊敗 97.52%使用 Python 的用戶

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def rotateRight(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""p = head# 長(zhǎng)度計(jì)算n = 1while p and p.next:n+=1p = p.next# 如果k為0 或者n小于等于1if(k == 0) or n <= 1:return head# nnt 獲取截?cái)辔恢?/span>nt = head# 成環(huán)p.next = head# 獲取截?cái)帱c(diǎn)for i in range(n - k % n - 1):nt = nt.next# 結(jié)果頭res = nt.next# 截?cái)嘌h(huán)nt.next = Nonereturn res