【C/C++面試考題】Reverse Linked List 反轉鏈結串列 (兩種方法)

經典的面試白板題。常見的Linked List Operation。

方法一：Data Structure 課本的方法

最常見的作法需要用到prev、current和next共3個指標。我自己都稱作毛毛蟲爬行法，因為 pointer 像是毛毛蟲一般向前蠕行。

要特別注意的是，傳進來的參數要用 pointed of pointer （指標的指標）才能順利改到外部的 Linked List。

把圖畫出來會比較清楚：

程式碼：

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)