Python程序:按k大小分组反转链表
假设我们有一个单链表,还有一个值k,我们需要反转每k个连续的节点组。
因此,如果输入类似于List = [1,2,3,4,5,6,7,8,9,10],k = 3,则输出将为[3, 2, 1, 6, 5, 4, 9, 8, 7, 10]
为了解决这个问题,我们将遵循以下步骤:
- tmp := 一个值为0的新节点
- tmp 的下一个节点 := node
- prev := null,curr := null
- lp := temp,lc := curr
- cnt := k
- 当curr不为空时,执行:
- prev := null
- 当cnt > 0且curr不为空时,执行:
- following := curr 的下一个节点
- curr 的下一个节点 := prev
- prev := curr,curr := following
- cnt := cnt - 1
- lp 的下一个节点 := prev,lc 的下一个节点 := curr
- lp := lc,lc := curr
- cnt := k
- 返回 tmp 的下一个节点
让我们来看下面的实现以更好地理解:
示例
class ListNode: def __init__(self, data, next = None): self.val = data self.next = next def make_list(elements): head = ListNode(elements[0]) for element in elements[1:]: ptr = head while ptr.next: ptr = ptr.next ptr.next = ListNode(element) return head def print_list(head): ptr = head print('[', end = "") while ptr: print(ptr.val, end = ", ") ptr = ptr.next print(']') class Solution: def solve(self, node, k): tmp = ListNode(0) tmp.next = node prev, curr = None, node lp, lc = tmp, curr cnt = k while curr: prev = None while cnt > 0 and curr: following = curr.next curr.next = prev prev, curr = curr, following cnt -= 1 lp.next, lc.next = prev, curr lp, lc = lc, curr cnt = k return tmp.next ob = Solution() head = make_list([1,2,3,4,5,6,7,8,9,10]) print_list(ob.solve(head, 3))
输入
[1,2,3,4,5,6,7,8,9,10], 3
输出
[3, 2, 1, 6, 5, 4, 9, 8, 7, 10, ]
广告