做爰全過(guò)程教育網(wǎng)站百度競(jìng)價(jià)排名官網(wǎng)
61. 旋轉(zhuǎn)鏈表
- 題目-中等難度
- 示例
- 1. 快慢指針找到分割位置
- 2. 連成環(huán)后截?cái)?/li>
題目-中等難度
相關(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