將一個鏈表中每k個數進行翻轉,末尾不足k個的數不做變化。
注意點:
不允許修改節點的值 只能用常量的額外空間例子:
輸入: head = 1->2->3->4->5, k = 2
輸出: 2->1->4->3->5
輸入: head = 1->2->3->4->5, k = 3
輸出: 3->2->1->4->5
這個題是Swap Nodes in Pairs的升級版。我們來看一下翻轉k個節點要進行哪些操作,A->B->C->D->E,現在我們要翻轉BCD三個節點。進行以下幾步:
C->B D->C B->E A->D 返回及節點B上面做了兩件事,把k個節點先翻轉(1、2兩步),再和前後兩個節點連接起來(3、4兩步)。
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head or k <= 1:
return head
dummy = ListNode(-1)
dummy.next = head
temp = dummy
while temp:
temp = self.reverseNextK(temp, k)
return dummy.next
def reverseNextK(self, head, k):
# Check if there are k nodes left
temp = head
for i in range(k):
if not temp.next:
return None
temp = temp.next
# The last node when the k nodes reversed
node = head.next
prev = head
curr = head.next
# Reverse k nodes
for i in range(k):
nextNode = curr.nex
curr.next = prev
prev = curr
curr = nextNode
# Connect with head and tail
node.next = curr
head.next = prev
return node
歡迎查看我的Github來獲得相關源碼。