LeetCode No.25 | StriveZs的博客

LeetCode No.25

LeetCode第二十五题

题目描述

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例:

给你这个链表:1->2->3->4->5

当 k = 2 时,应当返回: 2->1->4->3->5

当 k = 3 时,应当返回: 3->2->1->4->5

 

说明:

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

代码

超时的版本

分析愿原因为引入了统计长度的代码和两个多次循环重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 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 reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
res = head
length = 0
# 计算长度
while head != None:
length += 1
head = head.next
if length < k:
return head
head = res
part = int(length / k) # 共有多少个整数组
yushu = length % k # 余数
num = 0
NodeList = []
# 使用栈
while True:
for i in range(k):
NodeList.append(head)
head = head.next
for i in range(k):
if i == 0 and num == 0:
res = NodeList.pop()
result = res
else:
res.next = NodeList.pop()
res = res.next
num += 1
if num == part:
if yushu != 0:
res.next = head
break
return result

if __name__ == '__main__':
ln1 = ListNode(val=1)
ln2 = ListNode(val=2)

ln1.next = ln2

s = Solution()
print(s.reverseKGroup(ln1,2).val)

改正版本

去掉了一重循环,变成交换次序的操作了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 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 reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
dummy = ListNode(val=0)
current = head
prev = dummy
next = ListNode(val=0)
dummy.next = head
length = 0
# 计算长度
while head != None:
length += 1
head = head.next
head = dummy.next # 恢复head
if length < k:
return head
part = int(length / k) # 共有多少个整数组
yushu = length % k # 余数
for i in range(part):
for j in range(k-1):
next = current.next
current.next = next.next
next.next = prev.next
prev.next = next
prev = current
current = prev.next

return dummy.next

if __name__ == '__main__':
ln1 = ListNode(val=1)
ln2 = ListNode(val=2)

ln1.next = ln2

s = Solution()
print(s.reverseKGroup(ln1,2).val)
StriveZs wechat
Hobby lead  creation, technology change world.