反转每个 K 元素子列表

Question

我无法将之前的列表与当前的反向列表连接起来。问题如下...

给定一个 LinkedList 的头部和一个数字“k”，从头部开始反转每个“k”大小的子列表。如果最后剩下的子列表少于“k”个元素，也将其反转。

我只是想保留一个 counter，它总是被更新以反转从列表的 head 开始的最大 k 大小的 sub_list。找到 end 应该在哪里，并让 start 指向列表的开头。

为了反转任何大小小于或等于 k 的列表，我只检查 end is None.

列表的start成为列表的末尾，因为end实际上指向k + 1节点，所以第一次迭代将k个节点的第一个反转与其余节点连接起来列表的 start.next = end，其中 start 指向反向列表的最后一个节点，end 指向另一个列表的开头。

我知道我的问题在于，在第二次迭代期间，当列表反转时，我失去了对之前列表的引用（我们可以将其视为上半部分）。例如，对于我的第一次迭代，列表

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8, k = 3

变成，

3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 7 -> 8

但是在第二次迭代之后我不再有前 3 个节点 sub_list

from __future__ import print_function


class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next

  def print_list(self):
    temp = self
    while temp is not None:
      print(temp.value, end=" ")
      temp = temp.next
    print()


def reverse_every_k_elements(head, k):
  start, end = head, head
  previous = None

  while end is not None:
    counter = k

    while end is not None and counter > 0:
      end = end.next
      counter -= 1
    
    sub_list = reverse(start, end)
    start.next = end
    start = end
    
    if previous:
      previous.next = end
    else:
      previous = end

  


def reverse(head, stop_node):
  previous = None

  while head is not stop_node:
    _next = head.next
    head.next = previous
    previous = head
    head = _next

  return previous


def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)
  head.next.next.next.next.next = Node(6)
  head.next.next.next.next.next.next = Node(7)
  head.next.next.next.next.next.next.next = Node(8)

  print("Nodes of original LinkedList are: ", end='')
  head.print_list()
  result = reverse_every_k_elements(head, 3)
  print("Nodes of reversed LinkedList are: ", end='')
  result.print_list()


main()

我不知道从这里到哪里去。

Answer 1

因为 end 是节点在反向部分之后，或者 - 否则 - 列表其余部分的第一个节点仍然是已处理，你不应该：

previous.next = end

被反转的部分现在作为第一个节点被 sub_list 引用，所以：

previous.next = sub_list

这是除反转之外唯一需要更新的 next link，因此不需要此更新：

start.next = end

当 previous 为 None 时，我们应该设置 head:

而不是 previous.next

head = sub_list

这些是最重要的更改。通过一些其他的改编，我们得到这个：

def reverse_every_k_elements(head, k):
  start, end = None, head

  while end is not None:
    previous = start 
    start = end

    counter = k
    while end is not None and counter > 0:
      end = end.next
      counter -= 1
    
    sub_list = reverse(start, end)
    
    # Here the magic (of linking the pieces) happens:
    if previous:
      previous.next = sub_list
    else:
      head = sub_list

  # Need to return the head...
  return head

反转每个 K 元素子列表

Reverse every K-element Sub-List

python

reverse

sublist

singly-linked-list