以给定大小的组反转链表

Question

给定一个链表，一次反转链表k的节点和return其修改后的列表。

k为正整数，小于等于链表长度。如果节点数不是k的倍数，那么最后遗漏的节点应该保持原样。

您不能更改列表节点中的值，只能更改节点本身。

但是当我使用下面的代码时，我的输出：[3,2,1,5,4]

如何以正确的方式做到这一点？

class Solution
{
    public static Node reverse(Node head, int k)
    {
        Node prev = null;
        Node dummy = head;
        int c = 0;

        while(dummy != null && c < k ) {
            Node next = dummy.next;
            dummy.next = prev;
            prev = dummy;
            dummy = next;
            c++;
        }
        if(dummy != null) {
            head.next = reverse(dummy,k);
        }
        return prev;
    }
}

Answer 1

首先，编写一个计算列表长度的方法。稍后，通过每次增加 c.

时增加一些计数器来跟踪您当前正在反转的项目的索引

稍后，与其在重复调用 reverse 方法之前检查 if (dummy != null)，不如检查列表中是否还有足够的元素 - 通过比较在以计数器开头。

Answer 2

我写一个辅助方法

private boolean areAtLeastNNodes(int n, Node head)

因此，在尝试反转任何东西之前，我会调用此方法。如果returns为假，我将弃权。

我自己的 areAtLeastNNodes() 版本是递归的，因为我觉得它更简单。它也可以是迭代的。

我的建议是对每个子列表传递两次，一次用于计数，一次用于反转。这感觉很浪费。这当然可以避免，但它会很复杂，我不想打扰。

Answer 3

使用递归不需要计算列表的长度。但是，指针操作有点棘手。

public static Node reverseK(Node head, int k)
{
    return reverseK(head, head, k, k);
}

private static Node reverseK(Node head, Node node, int i, int k)
{
    // we reached a final sequence of length < k, return the current head
    if(node == null) 
        return head;
    
    if(i == 1)
    {           
        // we reached the end of a sequence of length k. 
        // Reverse the next sequence, return the new head.
        head.next = reverseK(node.next, node.next, k, k);
        return node;
    }
    
    // Store current next as it will be modified by the recursive call.
    Node next = node.next;
    
    Node newHead = reverseK(head, node.next, i-1, k);

    // If the current sequence was of length k, reverse pointers.
    if(newHead != head)
    {
        next.next = node;
    }
    
    return newHead;
}

测试：

int[] a = {1, 2, 3, 4, 5};

Node head = build(a);

print(head);

head = reverseK(head, 3);

print(head);

输出：

1 2 3 4 5 
3 2 1 4 5

Answer 4

我会考虑使用模数 k 的方法。在迭代的每一步，当前节点都可以从函数调用者或递归调用的结果中获取其“下一个”字段的值。

Python代码：

def print_list(node, k):
  i = 0
  s = ""
  while node:
    s += node['val']
    node = get_next(node)
    if i == k - 1:
      s += " "
    i = (i + 1) % k
  print(s)

def get_next(node):
  return node['next']

def set_next(node, new_next):
  node['next'] = new_next


# Returns (this_block_head, next_block_head)
def reverse(node, k, new_next=None, m=0):
  if k == 1:
    return (node, None)

  # We use 'this_block_head' as a signal
  # that when returns this current node,
  # it means the block's length is less than
  # k, and therefore will not be reversed.

  if not node:
    return (None, None) if m == 0 else (new_next, None)

  # The first node in
  # a block doesn't get
  # a next parameter and
  # must get it from the
  # recursive call.

  next_param = None if m == k - 1 else node

  (this_block_head, next_block_head) = reverse(get_next(node), k, next_param, (m + 1) % k)

  if this_block_head == node:
    # When 'new_next' is null,
    # this is a beginning of a block
    # so the caller needs the node
    # as its 'this_block_head'.
    return (new_next if new_next else node, None)

  # The last in the block,
  # which will become first,
  # here 'this_block_head' is
  # actually 'next_block_head'
  if m == k - 1:
    set_next(node, new_next)
    return (node, this_block_head)

  set_next(node, next_block_head if m == 0 else new_next)
  return (this_block_head, next_block_head)

输出：

def reset_list():
  global a, b, c, d, e, f
  f = {'val': 'f', 'next': None}
  e = {'val': 'e', 'next': f}
  d = {'val': 'd', 'next': e}
  c = {'val': 'c', 'next': d}
  b = {'val': 'b', 'next': c}
  a = {'val': 'a', 'next': b}

reset_list()
print_list(a, 6)  # abcdef
reverse(a, 2)
print_list(b, 2)  # ba dc fe

print("")

reset_list()
print_list(a, 6)  # abcdef
reverse(a, 3)
print_list(c, 3)  # cba fed

print("")

reset_list()
print_list(a, 6)  # abcdef
reverse(a, 4)
print_list(d, 4)  # dcba ef

Answer 5

你可以这样做，

对于以下示例，您将收到此回复

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

public class Main {

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;

        System.out.println(reverse(n1, n1, n1.next, 4));
    }

    public static Node reverse(Node fst, Node lst, Node nxt, int k) {
        if (k == 1) {
            return fst;
        } else {
            Node m1 = fst;
            Node m2 = nxt.next;

            fst = nxt;
            fst.next = m1;
            lst.next = m2;

            return reverse(fst, lst, lst.next, --k);
        }
    }
}

class Node {
    public int val;
    public Node next;

    public Node(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        if (next == null) {
            return "" + val;
        } return val + " -> " + next.toString();
    }
}

以给定大小的组反转链表

Reverse a Linked List in groups of given size

java

algorithm

linked-list