反轉鏈接列表中的每個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; 
}