經典的面試白板題。常見的Linked List Operation。
方法一:Data Structure 課本的方法
最常見的作法需要用到prev、current和next共3個指標。我自己都稱作毛毛蟲爬行法,因為 pointer 像是毛毛蟲一般向前蠕行。
要特別注意的是,傳進來的參數要用 pointed of pointer (指標的指標)才能順利改到外部的 Linked List。
把圖畫出來會比較清楚:

Reverse Linked List Gif Discription
程式碼:
struct Node{
int content;
struct node* next;
}
void reverse(struct Node **h){
int *prev = NULL;
int *current = *h;
int *next = NULL
while ( *current != NULL){
// Store next
next = *current -> next;
// Reverse current node's pointer
*current -> next = *prev;
// Move pointers one position ahead.
*prev = *current;
*current = *next;
}
}
Time Complexity: O(N)
Space Complexity: O(1)
方法二:偷吃步,活用腦袋用的。
想到了嗎?就是把整個串列印到 Arrry 裡,再反過來 Print 到鏈結串列中。
奇葩對吧?
但不是太實用,因為你必須用 malloc 要出記憶體空間,還要記得 free。
就當作是「頭腦體操」就好
Time Complexity: O(N)
Space Complexity: O(N)
留言