Description
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Note:
- Only constant extra memory is allowed.
- You may not alter the values in the list’s nodes, only nodes itself may be changed.
Solutions
0. 错误代码
要知道错在那里!
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head:
return None
if k < 2:
return head
stack = []
node = head
for _ in range(k):
if not node:
return head
stack.append(node)
node = node.next
new_head = stack.pop()
new_node = new_head
for _ in range(k-1):
new_node.next = stack.pop()
new_node = new_node.next
while node:
cur = node
for _ in range(k):
if not cur:
new_node.next = node
return new_head
stack.append(cur)
cur = cur.next
new_cur = stack.pop()
cur_node = new_cur
for _ in range(k-1):
cur_node.next = stack.pop()
cur_node = cur_node.next
new_node.next = new_cur
new_node = new_node.next
node = cur
return new_head
# Wrong Answer
# Runtime: 32 ms
# Your input
# [1,2,3,4,5]
# 2
# Output
# [2,1,4,5]
# Expected
# [2,1,4,3,5]
1. Recursion + Stack
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head:
return None
if k < 2:
return head
stack = []
node = head
for _ in range(k):
if not node:
return head
stack.append(node)
node = node.next
new_head = stack.pop()
new_node = new_head
for _ in range(k-1):
new_node.next = stack.pop()
new_node = new_node.next
new_node.next = self.reverseKGroup(node, k)
return new_head
# 81/81 cases passed (48 ms)
# Your runtime beats 75.41 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.7 MB)
2. Direct
反转硬刚。
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if head is None or k < 2:
return head
next_head = head
for i in range(k - 1):
next_head = next_head.next
if next_head is None:
return head
ret = next_head
current = head
while next_head:
tail = current
prev = None
for i in range(k):
if next_head:
next_head = next_head.next
_next = current.next
current.next = prev
prev = current
current = _next
tail.next = next_head or current
return ret
# 81/81 cases passed (44 ms)
# Your runtime beats 89.73 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.8 MB)