經典的面試白板題。常見的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)

最後修改日期: 18 5 月 2020

留言

撰寫回覆或留言

發佈留言必須填寫的電子郵件地址不會公開。