leetcode面試題 02.06. 回文鏈表，解題心路
目錄- leetcode面試題 02.06. 回文鏈表，解題心路
- 1、題目描述
- 2、java語言題解一
- 3、java語言題解二
- 4、C語言題解一
1、題目描述
撰寫一個函式，檢查輸入的鏈表是否是回文的，如圖：
試題鏈接：https://leetcode-cn.com/problems/palindrome-linked-list-lcci/
2、java語言題解一
看到該題，首先想打到的就是使用自己最拿手的語言java來做，首先，我們先來觀查題目所給鏈表的結構：
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
由于題目中要求判斷一個鏈表是否回文，因此很自然的一個想法就是，將鏈表變數，取出其中的值，放在一個有序的容器中，在java中很自然的就想到了list集合，于是就有了下述的解法：
public static boolean isPalindrome(ListNode head) {
List list = new ArrayList();
//定義一個輔助指標，用來遍歷鏈表
ListNode pCurrent = head;
//當鏈表不為null時，就一直回圈
while (pCurrent != null) {
//將該數保存到陣列中
list.add(pCurrent.val);
pCurrent = pCurrent.next;
}
//遍歷集合，看首尾是否相等
for(int i = 0;i < list.size() / 2;i++) {
if(!list.get(i).equals(list.get(list.size() - i - 1))) {
return false;
}
}
return true;
}
演算法效果：
可以看出，該演算法在java的提交記錄中，時間稍微較慢，當時所需要的記憶體確實最少的，然而，計算機程式比較關心的是演算法的執行效率，因此該演算法還得進行改進，
3、java語言題解二
由于上述的演算法的執行時間太長，猜想是不是因為使用了List集合而導致的，但是，如果不適用集合，我們的先獲取到該鏈表的長度，然后定義一個大小剛剛適合的陣列，代碼如下：
public static boolean isPalindrome(ListNode head) {
//定義一個輔助指標，用來遍歷鏈表
ListNode pCurrent = head;
//當鏈表不為null時，就一直回圈
int count = 0;
while (pCurrent != null) {
//計數
count++;
pCurrent = pCurrent.next;
}
//再來一論，裝進陣列
pCurrent = head;
int[] arr = new int[count];
for(int i = 0;i < count;i++) {
arr[i] = pCurrent.val;
pCurrent = pCurrent.next;
}
//遍歷集合，看首尾是否相等
for(int i = 0;i < count / 2;i++) {
if(arr[i] != arr[count - i - 1]) {
return false;
}
}
return true;
}
演算法效果：
可以看出，用陣列代替集合，增加一次回圈后的效率得到大幅度的提升，
4、C語言題解一
奈何，博主目前還是一個本科大學生，在資料結構與演算法這門課上垂死掙扎，而考試只允許用C來作答，因此，只有用C語言重寫上述的java演算法，
- 先來看看在C語言中，題目給出的鏈表的結構題型別
struct ListNode {
int val;
struct ListNode *next;
};
接下來，用C語言來實作上述的java題解二：
bool isPalindrome(struct ListNode* head){
//定義一個輔助指標，用來遍歷鏈表
struct ListNode* pCurrent = head;
//當鏈表不為null時，就一直回圈
int count = 0;
while (pCurrent != NULL) {
//計數
count++;
pCurrent = pCurrent->next;
}
if(count == 0)
return true;
//再來一論，裝進陣列
pCurrent = head;
int arr[count];
for(int i = 0;i < count;i++) {
arr[i] = pCurrent->val;
pCurrent = pCurrent->next;
}
//遍歷集合，看首尾是否相等
for(int i = 0;i < count / 2;i++) {
if(arr[i] != arr[count - i - 1]) {
return false;
}
}
return true;
}
演算法效果：
由執行用時可以看出，在C語言的解法中，該演算法并不是最優解，
除此之外，還有另外一種思路，就是將鏈表拆分成兩部分，然后使得一部分反轉，后遍歷兩個鏈表，觀察是否相等，但是，該方法經過博主測驗后，發現其效率還不如上述解法高效，因此不在敘述，后續如果有新的更高效解法在來敘述，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205855.html
標籤：其他
上一篇：洗掉鏈表的倒數第N個節點
下一篇：把字串轉換成整數