反转链接列表中的每个k块节点

Question

我试图解决这个反转链接列表中每个k块节点的问题。我在每个外部while循环中处理2 * k个元素。可以通过在每个外部while循环中处理k个元素来完成，还是不使用hasknodes（）函数？

样品输入：1-> 2-> 3-> 4-> 5和K = 3

示例输出：3-> 2-> 1-> 4-> 5

struct node *rev(struct node *head,int k) 
    { 
     if(k == 0 || k == 1) { 
      return head; 
     } 
     int i; 
     struct node *prev,*temp,*curr,*newhead,*p,*thead; 
     p = head; 
     thead = head; 
     newhead = NULL; 
     while(p && hasknodes(p,k)) { 
      prev = NULL; 
      curr = p; 
      i = 0; 
      while(curr && i < k) { 
       temp = curr->next; 
       curr->next = prev; 
       prev = curr; 
       curr= temp; 
       i++; 
      } 
      if(newhead == NULL) { 
       newhead = prev; 
      } 
      else { 
       thead->next = prev; 
      } 
      p->next = curr; 
      head = p; 
      if(p) { 
       p = p->next; 
      } 
     } 
     if(newhead == NULL) { 
      return head; 
     } 
     return newhead; 
    } 
//The function hasknodes(p,k) checks if there are k elements present from the current position p. 

Answer 1

你其实不需要调用函数hasknodes;而是开始拾取节点并以相反的顺序链接它们（如同在内部while循环中那样），并且如果您提前到达列表的末尾，则重新添加反向列表的元素。然而，这种方法的缺点是代码变得更复杂一点。作为第一个评论者写道：O（2 * n）实际上与O（n）相同，因为O（n）意味着您的问题可以在时间按比例到n解决。所以，你已经基本完成了:-)

Answer 2

将倒车看作是从一个列表中弹出并推向另一个列表是有帮助的。您还需要知道前一个k块的尾部才能追加下一个。因此，在伪代码：

// let list be the head of the input list 
prev_tail = sentinel; // fake previous tail node to append the first block 
while list is not NULL 
    tail = list 
    block = NULL 
    for k times and while list isn't NULL 
    push(block, pop(list)) 
    prev_tail->next = block 
    prev_tail = tail; 
return sentinel->next; 

在C，其中push和pop以通常的方式实现

现在：

typedef struct node_s { 
    struct node_s *next; 
    ... 
} Node; 

Node *reverse_blocks(Node *list, int k) { 
    Node sentinel[1] = {{NULL}}; 
    Node *prev_tail = sentinel; 
    while (list) { 
    Node *block = NULL; 
    Node *tail = list; 
    for (int i = 0; list && i < k; i++) { 
     Node *pop = list; 
     list = list->next; 
     pop->next = block; // push(block, pop) 
     block = pop; 
    } 
    prev_tail->next = block; 
    prev_tail = tail; 
    } 
    return sentinel->next; 
} 

Answer 3

你可以写一个简单的递归解决方案：

struct node *reverse (struct node *head, int k) 
{ 
    struct node* current = head; 
    struct node* next = NULL; 
    struct node* prev = NULL; 
    int count = 0; 

    /*reverse first k nodes of the linked list */ 
    while (current != NULL && count < k) 
    { 
     next = current->next; 
     current->next = prev; 
     prev = current; 
     current = next; 
     count++; 
    } 

    /* next is now a pointer to (k+1)th node,Recursively call for the 
     list starting from current.And make rest of the list as next of first node */ 
    if(next != NULL) 
    { 
     head->next = reverse(next, k); 
    } 

    /* prev is new head of the input list */ 
    return prev; 
}