倒車單鏈表當一個塊的大小被給予

有一個單獨連接的鏈表和一個塊的大小是given.For例如，如果我的鏈表是1->2->3->4->5->6->7->8-NULL和我的塊大小4然後反轉第一4元素，然後第二個4個元素。問題的輸出應該是4->3->2->1->8->7->6->5-NULL倒車單鏈表當一個塊的大小被給予

我在考慮將鏈表分割成大小爲4的段，然後對其進行反轉。但是這樣我就不得不使用很多額外的節點，這根本不是所期望的。空間複雜性應該保持在最低限度。

如果有人能提供更好的解決方案，將額外節點的使用保持在最低限度，這將是非常可觀的。

來源

2011-08-08 Poulami

我想這...似乎很好地工作......

node* reverse(node* head) // function to reverse a list 
{ 
    node* new_head = NULL; 
    while(head != NULL) 
    { 
     node* next = head->next; 
     head->next = new_head; 
     new_head = head; 
     head = next; 
    } 
    return new_head; 
} 

node* reverse_by_block(node* head, int block) 
{ 
    if(head == NULL) 
      return head; 

    node* tmp = head; 
    node* new_head = head; 
    node* new_tail = NULL; 

    int count = block; 
    while(tmp != NULL && count--) 
    { 
     new_tail = tmp; 
     tmp = tmp->next; 
    } 

    new_tail->next = NULL; 
    new_tail = new_head; 
    new_head = reverse(new_head); 
    new_tail->next = reverse_by_block(tmp,block); 

    return new_head; 
}

來源

2011-08-08 18:10:31 joshu

有想法。你的prg使用5個額外的節點，需要在那工作。 – Poulami

節點只是指針...點是沒有使用xtra內存。 – joshu

- 感謝它的幫助！ – Poulami

您可以使用下一個3次提前交換當前元素：1234,2134,2314,2341。然後執行兩次獲得3421.然後一次獲得4321.然後前進4個步驟並重復下一個過程塊。

來源

2011-08-08 13:24:43 LaC

我有扭轉節點不僅僅是數據元素。 – Poulami

是的。要交換A和B，P是A之前的節點（在掃描過程中記錄了這一點），請執行P.next = B，A.next = B.next，B.next = A. – LaC

這可以線性時間來完成，以恆定的空間。下面是簡要說明：

拆分鏈表成兩個部分通過塊大小


int split(node* head, node** listA, node** listB size_t block_size) 
{ 
node* cur = head; 

while(block_size && cur) 
{ 
    cur = cur->next; 
    --block_size; 
} 
if(!cur) { /* error : invalid block size */ return -1; } 
*listA = head; 
*listB = cur->next; 
cur->next = NULL; /* terminate list A */ 
return 0; 
}

反向兩個子部分，（使用非遞歸線性時，恆定空間功能）
```
reverse(listA); 
reverse(listB); 
```

鏈接它們以獲得所需的鏈接列表。


cur = *listA; 
/* goto last but one element of listA */ 
while(cur->next) cur = cur->next; 
cur->next = *listB;

來源

2011-08-11 05:35:58

倒車單鏈表當一個塊的大小被給予

回答

相關問題