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");
}

登錄后復制