如何以相反的順序打印單鏈表？

Question

struct node 
{ 
    int info; 
    struct node *next; 
}; 
typedef struct node node; 

void *printRev(node *head){ 
     int count=0; 
     int i; 
     node *beforeFin; 
     node *tempHead; 
     tempHead = head; 

     while(tempHead->next != NULL){ 
      count++; 
      tempHead->next = tempHead->next->next; //LAST ITERATION SHOULD BE AT THE END OF LIST 
     } 
     printf("COUNT IS: %d\n", count); 
     for(i = 0; i <= count; i++){ 
     beforeFin = Prev(head, tempHead->next); 
     printf("%d", beforeFin->info); 
     } 
     printf("\n"); 
    } 

，現在這一打印出：

COUNT IS: 3 
Segmentation fault (core dumped) 

Prev給定的指針之前返回一個指針到節點（tempHead->next）我的意思是這個以相反的順序使用打印出單鏈表for循環上面。因此給定節點的->info應該在下面的例子中返回5（在第一次迭代之後）。

在打印計數的printf之前，tempHead->next應指向最終節點。

現在我傳遞2 3 5 4，這是給我的4 ID前面的計數像這樣打印出來4 5 3 2

我將不勝感激給予任何幫助，我是一個初學者，你也許能夠告訴。謝謝大家！

我可以做到這一點使用遞歸，但我想學習弄清楚這種方法。

Answer 1

要以相反順序打印單個鏈表，可以使用遞歸函數。你必須步入遞歸結束並打印列表的元素你離開遞歸函數權之前：

void printReverse(node *act) 
{ 
    if (act == NULL)   // terminate if end of list is reached 
     return; 

    printRev(act->next);  // print next node 
    printf("%d ", act->info); // print this node 
} 

如果你不想使用遞歸，你當然可以顛倒列表，然後打印清單並最終再次翻轉。

反轉列表並不困難。遍歷列表，獲取每個元素並將其重新排列在列表頭部的前面。

node * reverse(node *head) 
{ 
    node *act, *prev; 
    if (head == NULL) 
     return; 

    prev = head; 
    act = head->next; 
    while (act != NULL) 
    { 
     prev->next = act->next; 
     act->next = head; 
     head = act; 
     act = prev->next; 
    } 
    return head; 
} 

void printReverse(node *head) 
{ 
    node *act; 

    act = reverse(head); 
    while (act != NULL) 
    { 
     printf("%d ", act->info); // print this node 
     act = act->next; 
    } 
    reverse(head); 
} 

Answer 2

正如你想避免遞歸，你需要先反轉列表。我在原始代碼中看到了一些嘗試，但看起來不正確。請嘗試以下操作：

node *current = head; 
if (current != NULL) { 
    node *prev = NULL; 
    for (node *next = current->next; ; next = (current = next)->next) { 
     current->next = prev; 
     prev = current; 
     if (next == NULL) 
      break; 
    } 
} 

然後current將指向列表的頭，你可以遍歷使用在列表中的next鏈接。請注意，它會修改您的原始列表，但這是預期的，因爲我瞭解原始要求。

Answer 3

遞歸算法的問題是，如果你像我這樣有點偏執，列表可能足夠大，導致遞歸調用總結和溢出堆棧。如果列表來自某些用戶輸入，那麼這可以用於拒絕服務攻擊。因此，我看到兩個合理的選擇：

1. 創建列表的反轉副本並打印該副本。
2. 反轉列表中的位置，打印它，可能會將其逆轉回來。

如果您在內存受限設置或大型列表中工作，後者會很有趣。

#include <stdio.h> 
#include <assert.h> 
#include <stdlib.h> 

struct node { 
    int value; 
    struct node * next; 
}; 

void reverse_inplace (struct node ** list) { 
    assert(list != NULL); 
    struct node * follow = NULL, * lead = *list; 
    while (lead != NULL) { 
    struct node * next = lead->next; 
    lead->next = follow; 
    follow = lead; 
    lead = next; 
    } 
    *list = follow; 
} 

void print (struct node const * head) { 
    printf("("); 
    while (head) { 
    printf("%d ", head->value); 
    head = head->next; 
    } 
    printf(")"); 
} 

void link (struct node * array, size_t count) { 
    struct node * follow = NULL; 
    while (count-->0) { 
    array[count].next = follow; 
    follow = &(array[count]); 
    } 
} 

void fill (struct node * list, int value, int const step) { 
    while (list != NULL) { 
    list->value = value; 
    value += step; 
    list = list->next; 
    } 
} 

int main() { 
    size_t const sizes[] = {1, 2, 6}; 
    size_t const num = 
    sizeof(sizes)/sizeof(sizes[0]); 
    size_t caseId = 0; 
    for (; caseId < num; ++caseId) { 
    struct node * head = 
     malloc(sizeof(*head) * sizes[caseId]); 
    printf("Case %zu: List of size %zu\n", 
     caseId, sizes[caseId]); 
    link(head, sizes[caseId]); 
    fill(head, caseId, caseId); 
    printf(" initial: "); 
    print(head); 
    printf(" \n"); 
    reverse_inplace(& head); 
    printf(" reversed: "); 
    print (head); 
    printf(" \n"); 
    reverse_inplace(& head); 
    free(head); 
    } 
    printf("Case %zu: empty list \n", caseId); 
    struct node * head = NULL; 
    printf(" initial: "); 
    print(head); 
    printf(" \n"); 
    reverse_inplace(& head); 
    printf(" reversed: "); 
    print(head); 
    printf(" \n"); 
    return 0; 
} 

（Live on ideone）