JavaScript 程式檢查單鏈表是否為迴文

---

單鏈表是一種線性資料結構，以非連續的方式儲存在記憶體中，每個塊透過儲存下一個塊的地址（也稱為節點）來連線。迴文可以解釋為一組字元、數字等，它從前面和後面讀取都是一樣的。我們將得到一個單鏈表，並必須找到節點中儲存的值從前面和後面是否相等。

輸入

1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null

輸出

Yes, the given linked list is a palindrome. 

解釋

我們可以看到第一個和最後一個節點具有相同的值，第二個和倒數第二個節點也一樣，依此類推，每個與前後距離相同的節點都具有相同的值。

輸入

1 -> 2 -> 3 -> 4 -> 2 -> 1 -> null

輸出

No, the given linked list is not a palindrome. 

解釋

這裡，第一個和第二個節點分別等於最後一個和倒數第二個節點，但之後的節點沒有相同的值。

使用棧

在這種方法中，我們將首先使用類建立一個連結串列，然後定義一些基本函式來將資料新增到連結串列中以及列印連結串列中存在的資料。

示例

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = "";    
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);
}

// function to find the string is palindrome or not
function check(head){
   var temp = head;
   var stack = []; // defining the stack    
   while(temp != null){
      stack.push(temp.value);
      temp = temp.next;
   }    
   temp = head;
   while(temp != null){
      if(temp.value != stack.pop()){
         return false;
      }
      temp = temp.next;
   }
   return true;
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(3,head, tail)
tail = add(2,head, tail)
tail = add(1,head, tail)
console.log("The given linked list is: ")
print(head)

// calling function to check if the current linked list is a palindrome or not 
if(check(head)){
   console.log("Yes, the given linked list is a palindrome");
}
else{
   console.log("No, the given linked list is not a palindrome");
}

時間和空間複雜度

以上程式碼的時間複雜度為 O(N)，其中 N 是連結串列的長度。

以上程式碼的空間複雜度為 O(N)，因為我們使用棧資料結構來儲存元素。

使用遞迴

在這種方法中，我們將首先找到給定連結串列的長度，然後使用遞迴遍歷到連結串列的中間。如果給定連結串列的長度為奇數，我們將返回中間節點的下一個節點，否則返回中間節點，並且對於每次呼叫，我們將從遞迴呼叫中獲取相應的節點。

示例

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = "";    
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);
}

// recursive function 
function recursion(head, number, odd){
   if(number == 0){
      if(odd){
         return head.next;
      }
      else{
         return head;
      }
   }
   var temp = recursion(head.next, number-1, odd);
   
   // if the current value is not equal then don't move to the next node
   
   // by this we will not reach null in the end 
   
   // indicated the not palindrome 
   
   if(temp.value != head.value){
      return temp;
   }
   else{
      return temp.next;
   }
}

// function to check if the given linked list is palindrome or not 
function check(head){
   var temp = head;
   var len = 0;

   // finding the length of the given linked list 
   while(temp != null){
      len++;
      temp = temp.next;
   }

   // calling the recursion function 
   if(recursion(head, Math.floor(len/2), len & 1) == null){
      return true;
   }
   else{
      return false;
   }
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(3,head, tail)
tail = add(2,head, tail)
tail = add(1,head, tail)
console.log("The given linked list is: ")
print(head)

// calling function to check if the current linked list is a palindrome or not 
if(check(head)){
   console.log("Yes, the given linked list is a palindrome");
}
else{
   console.log("No, the given linked list is not a palindrome");
}

結論

在本教程中，我們實現了 JavaScript 程式來檢查給定的連結串列節點是否包含迴文中的值。我們使用棧和遞迴實現了兩個程式碼，它們的時間複雜度為 O(N)，棧的空間複雜度為 O(N)，遞迴方法的空間複雜度為 O(1)（僅當不考慮遞迴呼叫資料時）。