如何反轉我在C中創建的鏈接列表

Question

我已經創建了一個鏈接列表，但無法想象如何反轉相同。我知道算法，但我認爲我在創建列表時犯了一個錯誤。反函數中的變化可能會起作用。 以下是代碼：

typedef struct Node{ 
    int data; 
    struct Node* next; 
} node; 
node* head; 
int count; 
void insertAtBegin(int value){ 
    if(head==NULL){ 
     head = (node*)malloc(sizeof(node)); 
     head->data = 0; 
     head->next = NULL; 
    } 
    node* newNode = (node*)malloc(sizeof(node)); 
    newNode->data = value; 
    newNode->next = head->next; 
    head->next = newNode; 
    count++; 
} 

void display(){ 
    node* temp = (node*)malloc(sizeof(node)); 
    temp = head; 
    while(temp->next!=NULL){ 
     printf("%d\t",temp->next->data); 
     temp = temp->next; 
    } 
    printf("\n"); 
} 

void reverse(){ 
    node *p, *q, *r; 

    p = q = r = head; 
    p = p->next->next; 
    q = q->next; 
    r->next = NULL; 
    q->next = r; 

    while (p != NULL){ 
     r = q; 
     q = p; 
     p = p->next; 
     q->next = r; 
    } 
    head = q; 
} 

void main(){ 
    insertAtBegin(5); 
    insertAtBegin(6); 
    display(); 
    reverse(); 
    display(); 
    printf("\nSize of linked list is %d",count); 
} 

Answer 1

比方說，你有以下列表：

head = n0 
n0 -> ... -> A -> B -> C -> D -> E -> ... -> nN -> NULL 

要扭轉到：

head = nN 
nN -> ... -> E -> D -> C -> B -> A -> ... -> n0 -> NULL 

現在，讓我們考慮的情況下，當名單的開始已經顛倒過來，並且您正在處理節點C。你當時的名單是：

head = B 
B -> A -> ... -> n0-> NULL 
tmpHead = C 
C -> D -> E ... -> nN -> NULL 

凡tmpHead是一個臨時變量，讓您不輸於C參考（如B.next現在指向A）你想：

1. 連接B到C使B來後C
2. 組頭C，反向列表的新頭
3. 保持D在臨時變量tmpHead，所以你仍然可以訪問它

然後倒車變爲：

node * tmp = tmpHead.next; // 3. part 1 
tmpHead.next = head;   // 1. 
head   = tmpHead;  // 2. 
tmpHead  = tmp;   // 3. part 2 

停止條件是相當明顯的：你必須停止，當你到達終點的名單，所以，當tmpHead是NULL。至於初始化，如head指向反轉部分和tmpHead指向非反轉部分。因此tmpHead必須設置爲head和head至NULL。

最後，你會得到下面的函數，其採取的一個指針列表的第一個節點作爲輸入參數

void reverse(node ** head) 
{ 
    node * tmpHead = (* head); 
    (* head)  = NULL; 

    while(tmpHead) 
    { 
    node * tmp = tmpHead->next; 
    tmpHead->next = (* head); 
    (* head)  = tmpHead; 
    tmpHead  = tmp; 
    } 
} 

注意，有一個「問題」與你插入一個新的節點方式您的列表開始：您始終保留一個「幻像」節點，其數據設置爲0，並且您致電head。所以，正如我所定義的那樣，列表中的第一個真正節點是您的head->next。這意味着您必須調用reverse這樣的功能：reverse(& (head->next))或稍微修改該功能。

此外，請注意，您不應該投射malloc的結果。 Do I cast the result of malloc?