單鏈接列表是迴文是否

Question

我有一個單一的鏈接列表。我想找到鏈接列表是迴文或不。 我已經以下面的一種方式實現了它。

bool palindromeOrNot(node *head) { 
    node *tailPointer; 
    node *headLocal=head; 
    node *reverseList=reverseLinkedListIteratively(head); 
    int response=1; 

    while(headLocal != NULL && reverseList!=NULL) { 
    if(headLocal->id==reverseList->id) { 
     headLocal=headLocal->next; 
     reverseList=reverseList->next; 
    } 
    else 
     return false; 
    } 

    if(headLocal == NULL && reverseList==NULL) 
    return fasle; 
    else 
    return true; 
} 

我正在顛倒原始鏈接列表，然後比較節點。如果一切都很好 然後我會返回1否則返回0.

有沒有更好的算法來解決這個問題。

Answer 1

你爲什麼使它複雜。 由於這是一個家庭work.i可以給你一個簡單的建議。我觀察到你只是比較你的代碼中的id。 假設你的ID是一個字符，爲什麼不簡單地遍歷列表並將字符存儲在一個數組中，然後檢查迴文。 您的方法只需簡單地顛倒鏈表一次並遍歷鏈表兩遍 完全在函數中有三個遍歷。

Answer 2

當我們比較鏈表和反轉列表時，我們實際上只需要比較列表的前半部分。如果正常列表的前半部分與反向列表的前半部分匹配，則正常列表的後半部分必須與反向列表的後半部分匹配。

Answer 3

Whether a single-linked list is Palindrome or not，也可以檢查without reversing the linked list

遞歸方法可以走近其中的指針指向鏈表的開始，&另一個指針從遞歸從最後返回時，將進行比較。

這裏是僞代碼：

int isPalindrome(**root,*head) 
{ 
if(!head) 
    return 1; 
else 
{ 
    int res = isPalindrome(root,head->next); 

    if(res == 0) 
     return 0; 
    int r = (*root)->data == head->data; 
    *root = (*root)->next; 
    return r; 
} 
} 

呼叫是由這樣的：isPalindrome(&root,root);

Answer 4

方法1（使用棧）

一個簡單的解決方案是使用列表的堆節點。這主要涉及三個步驟。

1. 從頭到尾遍歷給定列表並推送每個訪問節點進行堆棧。
2. 再次遍歷列表。對於每個訪問節點，從堆棧中彈出節點，並將彈出節點的數據與當前訪問的節點進行比較。
3. 如果所有節點匹配，則返回true，否則返回false。

上述方法的時間複雜度是O（n），但它需要O（n）額外的空間。以下方法用恆定的額外空間解決這個問題

方法2（通過反轉列表）

此方法需要O（n）的時間和O（1）的額外空間。

1. 獲取鏈接列表的中間部分。
2. 顛倒鏈表的後半部分。
3. 檢查前半部分和後半部分是否相同。
4. 再次反轉下半年和附加回上半年

方法3（使用遞歸）

使用兩個指針左右構造原始鏈接列表。使用遞歸來左右移動，並在每次遞歸調用中檢查以下內容。

1. 子列表是迴文。
2. 當前左右值相符。

如果上述兩個條件均爲真，則返回true。

這個想法是使用函數調用堆棧作爲容器。遞歸遍歷直到列表結束。當我們從最後一個NULL返回時，我們將在最後一個節點。最後一個節點與列表的第一個節點進行比較。

爲了訪問列表的第一個節點，我們需要列表頭在遞歸的最後一次調用中可用。因此我們也將頭傳遞給遞歸函數。如果兩者匹配，我們需要比較（2，n-2）個節點。當遞歸回落到（n-2）nd節點時，我們需要從頭開始參考第二個節點。我們在前一個調用中前進頭指針，以引用列表中的下一個節點。

但是，識別雙指針的技巧。傳遞單指針和傳值一樣好，我們會一次又一次地傳遞相同的指針。我們需要傳遞頭指針的地址以反映父遞歸調用的變化。

更多：geeksforgeeks

Answer 5

我想你可以在有O（1）內存使用和同爲O（n）速度方面得到較好的解決。通過處理鏈接列表。您不必創建鏈接列表的反轉副本。但是這種方法破壞了列表。你將不得不將它縫合到位，但運行時間仍然是O（n）。

isPalindrome的快速版本的代碼基本上找到鏈接列表的中間，然後從邏輯上將鏈接列表分成2個部分。它只反轉了第一部分，並與另一部分進行比較。壞的部分是由於第一個鏈表上的塊就地反轉而破壞了鏈表。但是，您可以將列表重新拼接在一起，並且仍然處於O（n）時間。

要看的功能是isPalindromeFast。我開始了，但還沒有完成完成。你可以在這裏運行代碼http://play.golang.org/p/3pb4hxdRIp。

這裏是Go的完整代碼。

package main 

import "fmt" 

type Node struct { 
    value string 
    next *Node 
} 

func (n *Node) Next() *Node { 
    return n.next 
} 

func (n *Node) Value() string { 
    return n.value 
} 

func (n *Node) Length() int { 
    length := 0 
    linkedList := n 
    for linkedList != nil { 
     length += 1 
     linkedList = linkedList.Next() 
    } 

    return length 
} 

func NewLinkedList(s string) *Node { 
    if len(s) == 0 { 
     return nil 
    } 

    headNode := &Node{string(s[0]), nil} 
    currentNode := headNode 

    for _, v := range s[1:] { 
     newNode := &Node{string(v), nil} 
     currentNode.next = newNode 
     currentNode = newNode 
    } 

    return headNode 
} 

func PrintLinkedList(linkedList *Node) { 
    for linkedList != nil { 
     fmt.Println(linkedList) 
     linkedList = linkedList.Next() 
    } 
} 

func ReverseList(linkedList *Node, endPoint int) *Node { 

    if endPoint == 1 { 
     return linkedList 
    } 

    first, next, lastNode := linkedList, linkedList, linkedList 
    lastNode = nil 

    for i := 0; i < endPoint; i++ { 
     next = first.Next() 
     first.next = lastNode 
     lastNode = first 
     first = next 

    } 

    return lastNode 

} 

// func StitchListsBackTogether(listA, listB, listC *Node, endOfListA int) *Node { 
// listAFixed := ReverseList(listA, endOfListA) 
// listStart := listAFixed 
// for listAFixed.Next() != nil { 
//  listAFixed = listAFixed.Next() 
// } 
// listAFixed.next = listB 

// return listStart 

// } 

func IsPalindromeFast(linkedList *Node) bool { 
    // Uses O(1) space and O(n) time 
    // However mutates and destroys list, so need to stitch list backtogether. Initial implementation StitchListsBackTogether 
    length := linkedList.Length() 

    endOfListA := length/2 
    endOfListB := length/2 

    if length%2 == 0 { 
     endOfListB += 1 
    } else { 
     endOfListB += 2 
    } 

    listA, listB := linkedList, linkedList 

    for i := 0; i < endOfListB-1; i++ { 
     listB = listB.Next() 
    } 

    listA = ReverseList(listA, endOfListA) 

    for listA != nil && listB != nil { 
     if listA.Value() != listB.Value() { 
      return false 
     } 
     listA = listA.Next() 
     listB = listB.Next() 
    } 

    return true 
} 

func IsPalindromeSlow(linkedList *Node) bool { 
    //Uses O(1) space and O(n^2) time 
    startPalidrome, endPalidrome := linkedList, linkedList 

    for endPalidrome.Next() != nil { 
     endPalidrome = endPalidrome.Next() 
    } 

    for startPalidrome != endPalidrome { 

     if startPalidrome.Value() != endPalidrome.Value() { 
      return false 
     } 

     if startPalidrome.Next() == endPalidrome { 
      return true 
     } 

     startPalidrome = startPalidrome.Next() 

     middlePalidrome := startPalidrome 

     for middlePalidrome.Next() != endPalidrome { 
      middlePalidrome = middlePalidrome.Next() 
     } 
     endPalidrome = middlePalidrome 

    } 

    return true 
} 

func main() { 

    fmt.Println(IsPalindromeSlow(NewLinkedList("ttoott"))) 
    fmt.Println(IsPalindromeFast(NewLinkedList("ttoott"))) 
    fmt.Println("") 
    fmt.Println(IsPalindromeSlow(NewLinkedList("ttott"))) 
    fmt.Println(IsPalindromeFast(NewLinkedList("ttott"))) 
    fmt.Println("") 
    fmt.Println(IsPalindromeSlow(NewLinkedList("hello"))) 
    fmt.Println(IsPalindromeFast(NewLinkedList("hello"))) 
    fmt.Println("") 
    fmt.Println(IsPalindromeSlow(NewLinkedList("ttto"))) 
    fmt.Println(IsPalindromeFast(NewLinkedList("ttto"))) 
    fmt.Println("") 
    fmt.Println(IsPalindromeSlow(NewLinkedList("tt"))) 
    fmt.Println(IsPalindromeFast(NewLinkedList("tt"))) 
    fmt.Println("") 
    fmt.Println(IsPalindromeSlow(NewLinkedList("t"))) 
    fmt.Println(IsPalindromeFast(NewLinkedList("t"))) 
    fmt.Println("") 
    fmt.Println(IsPalindromeSlow(NewLinkedList("tto3tt"))) 
    fmt.Println(IsPalindromeFast(NewLinkedList("tto3tt"))) 
    fmt.Println("") 

} 

Answer 6

這是我對這個問題的解決方案。爲了測試它，我使用整數而不是字符，例如我用1,4,1,4,1代替「adada」。您可以將int更改爲字符，並且所有內容都應該仍然有效

struct Node 
{ 
    Node(int in) : data(in) {} 
    int data; 
    Node* next; 
}; 

//This function will find recursively call itself until last element and than it will start //comparing. To compare with correct element from the beginning a paramater called pos is used 
bool palindromeStart(Node* first, Node* last, size_t pos, size_t middlePos) 
{ 
    if (last->next != NULL) 
    { 
     if (palindromeStart(first, last->next, pos + 1, middlePos) == false) 
      return false; 
    } 

    size_t curPos = middlePos - pos; 
    while (curPos--) 
     first = first->next; 

    if (first->data != last->data) 
     return false; 
    return true; 
} 

bool isPalindrome(Node* head) 
{ 
    Node* n1 = head; 
    Node* n2 = head; 
    size_t middlePos = 0; 
    while (true) 
    { 
     if (n2 == nullptr) 
     { 
      --middlePos; 
      break; 
     } 
     else if (n2->next == nullptr) 
     { 
      break; 
     } 

     n2 = n2->next->next; 
     n1 = n1->next; 
     ++middlePos; 
    } // Until now I just find the middle 

    return palindromeStart(head, n1, 0, middlePos); 
} 

int main() 
{ 
     Node* n = new Node(1); 
     Node* n1 = new Node(4); 
     Node* n2 = new Node(4); 
     Node* n3 = new Node(1); 
     Node* n4 = new Node(1); 



     n->next = n1; 
     n1->next = n2; 
     n2->next = n3; 
     n3->next = nullptr; 
     //n3->next = n4; 
     //n4->next = nullptr; 

     std::cout << isPalindrome(n); 


} 

Answer 7

只是reverse鏈表的一半。並開始比較。您不需要reverse整個鏈表。

Answer 8

我認爲最佳的解決方案是不使用額外的空間，這意味着不使用一個新的反向LL ...這個想法是利用遞歸使用的操作棧......因爲當遞歸已經達到在基本情況下，它會從最後一個插入的節點（這是LL的最後一個節點）開始彈出堆棧...我實際上已經完成了這一步的一半，並且撞到了牆上。一些根和最後一個節點是如何偏移...看我的代碼

public LLNode compare(LLNode root) { 
    // 
    // base case, popping opr stack, 
    // this should be the last node on the linked list 
    if (root.next == null) { 
     System.out.printf("Poping stack: %d\n", root.data); 
     return root; 
    } 

    // 
    // push the functions to the opr stack 
    System.out.printf("pushing %d to the stack\n", root.next.data); 
    LLNode last = compare(root.next); 
    System.out.printf("On the way back: %d, root: %d\n", last.data, root.data); 

    return root; 
} 

和輸出是這樣的：

The list looks like this: 
1 2 3 4 3 2 1 
pushing 2 to the stack 
pushing 3 to the stack 
pushing 4 to the stack 
pushing 3 to the stack 
pushing 2 to the stack 
pushing 1 to the stack 
Poping stack: 1 
On the way back: 1, root: 2 
On the way back: 2, root: 3 
On the way back: 3, root: 4 
On the way back: 4, root: 3 
On the way back: 3, root: 2 
On the way back: 2, root: 1 

如果你能弄明白，請讓我知道

Answer 9

下面是我使用向量的實現。希望它能幫助別人。

node.h文件作爲以下的

#ifndef node_h 
#define node_h 

class LinkedList 
{ 

private: 
    struct node 
    { 
     int data; 
     node *next; 
    }; 
    node *head; 

public: 
    LinkedList(); 
    node *createNode (int key); 
    void appendNodeBack (int key); 
    void printList(); 
    bool isPalindrome (LinkedList list); 

}; 
#endif 

node.cpp文件。

#include <vector> 
#include "node.h" 

LinkedList::LinkedList():head(NULL) {} 

LinkedList::node *LinkedList::createNode (int key) 
{ 
    node *newNode = new node; 
    newNode->data = key; 
    newNode->next = NULL; 
    return newNode; 
} 

void LinkedList::appendNodeBack (int key) 
{ 
    node *newNode = createNode (key); 

    //if tree is empty 
    if (head == NULL) 
    { 
     head = newNode; 
     return; 
    } 

    //if tree is not empty 
    //traverse to the last node in the list 
    node *temp = head; 
    while (temp->next != NULL) 
     temp = temp->next; 

    temp->next = newNode; 
} 

void LinkedList::printList() 
{ 
    //if tree is empty 
    if (head == NULL) 
    { 
     std::cout << "Tree is empty!\n"; 
     return; 
    } 

    //if tree not empty 
    node *temp = head; 
    while (temp != NULL) 
    { 
     std::cout << temp->data<<"-->"; 
     temp = temp->next; 

    } 
    std::cout << "NULL\n"; 
} 

bool LinkedList::isPalindrome (LinkedList list) 
{ 
    node *temp = head; 

    unsigned int count = 0; 

    //push all elements of the list in an array, and count total number of nodes 
    std::vector<int> array; 

    while (temp != NULL) 
    { 
     count++; 
     array.push_back (temp->data); 
     temp = temp->next; 
    } 

    bool check = true; 

    for (unsigned int i = 0, j = array.size() -1; i < j; i++, j--) 
    { 
     if (array.at(i) != array.at(j)) 
      check = false; 
    } 

    return check; 
} 

main.cpp文件如下。

#include <iostream> 
#include "node.cpp" 

int main() 
{ 
    LinkedList list; 
    list.appendNodeBack (2); 
    list.appendNodeBack (3); 
    list.appendNodeBack (11); 
    list.appendNodeBack (4); 
    list.appendNodeBack (6); 
    list.appendNodeBack (4); 
    list.appendNodeBack (11); 
    list.appendNodeBack (3); 
    list.appendNodeBack (2); 

    list.printList(); 

    if (list.isPalindrome (list)) 
     std::cout << "List is a palindrome!\n"; 
    else 
     std::cout << "List is NOT a palindrome!\n"; 

    return 0; 
} 

Answer 10

在java中，存放在字符串變量的值，並使用字符串生成器

String s = ""; 
while (node != null){ 
s = s+ node1.value; 
node = node.next; 
} 
StringBuilder reverseString = new StringBuilder(s); 
reverseString = reverseString.reverse(); 
String s1 = new String(reverseString); 

System.out.println(s.equals(s1)); 

Answer 11

有一對夫婦的方式做到這一點逆轉。解決的辦法之一可能是象下面這樣：

1. 找到中間節點在一個給定的LinkedList
2. 反向下半年
3. 然後，比較上半年

該解決方案具有O（ n）時間複雜性。這是C＃中的一個示例實現。

// Returns length of a LinkedList 
    private static int GetLength(Node head) 
    { 
     var length = 0; 

     if (head == null) 
      return length; 

     var runner = head; 
     while (runner != null) 
     { 
      length++; 
      runner = runner.Next; 
     } 

     return length; 
    } 

    // Compares two LinkedLists 
    private static bool Compare(Node head1, Node head2) 
    { 
     // Get Lengths 
     var len1 = GetLength(head1); 
     var len2 = GetLength(head2); 

     if (len1 != len2) 
      return false; 

     var runner1 = head1; 
     var runner2 = head2; 

     while (runner1 != null && runner2 != null) 
     { 
      if (runner1.Data != runner2.Data) 
       return false; 

      runner1 = runner1.Next; 
      runner2 = runner2.Next; 
     } 

     return true; 
    } 

    // Reverse a LinkedList 
    private static Node Reverse(Node head) 
    { 
     if (head == null) 
      return null; 

     Node prev = null; 
     Node next; 
     var current = head; 

     while (current != null) 
     { 
      next = current.Next; 
      current.Next = prev; 
      prev = current; 
      current = next; 
     } 

     return prev; 
    } 

    private static bool IsPalindrome(Node head) 
    { 
     if (head == null) 
      return false; 

     if (head.Next == null) 
      return true; 

     var slowPrev = head; 
     var slow = head; 
     var fast = head; 

     while (fast != null && fast.Next != null) 
     { 
      fast = fast.Next.Next; 
      slowPrev = slow; 
      slow = slow.Next; 
     } 

     Node firstHalf; 
     Node secondHalf; 
     if (fast == null) 
     { 
      secondHalf = slow; 
      slowPrev.Next = null; 
      firstHalf = head; 
     } 
     else 
     { 
      secondHalf = slow.Next; 
      slowPrev.Next = null; 
      firstHalf = head; 
     } 

     return Compare(firstHalf, Reverse(secondHalf)); 
    } 

Answer 12

也可以檢查它使用數組，首先遍歷從它的根鏈表和每個節點的數據字段存儲到一個數組，然後逆轉該數組，然後通過一個元件比較這兩個陣列之一。下面是該程序

bool isPalindrome(Node *head) 
{ 
     int i=0,j,n=0,arr1[50],arr2[50]; 
     struct Node *current; 
     current=head; 
     while(current!=NULL) 
     { 
      arr1[i]=current->data; 
      i++; 
      n++; 
      current=current->next; 
     } 
     j=0; 
     for(i=n-1;i>=0;i--) 
     { 
      arr2[j]=arr1[i]; 
      j++; 
     } 
     for(i=0;i<n;i++) 
     { 
      if(arr1[i]!=arr2[i]) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 

Answer 13

Python程序檢查輸入鏈表是迴文與否

class Node: 
    def __init__(self, val): 
    self.data=val 
    self.next=None 

def rec_palindrome(slow, fast): 
    if fast == None: 
     # Even number of nodes 
     return 0, slow 
    elif fast.next == None: 
     return -1, slow 
    else: 
     res, ptr = rec_palindrome(slow.next, fast.next.next) 
     if res == -1: 
     tmp = ptr.next 
     if tmp.data != slow.data: 
      return 1, None 
     else: 
      return 0, tmp.next 
     elif res == 1: 
     return 1, None 
     elif res == 0: 
     if ptr.data != slow.data: 
      return 1, None 
     else: 
      return 0, ptr.next 
     else: 
     return res, None 

class LinkedList: 
    def __init__(self): 
    self.head = None 

    def append(self, node): 
    if self.head == None: 
     self.head = node 
    else: 
     cur = self.head 
     while cur.next != None: 
      cur = cur.next 
     cur.next = node 

    def display(self, msg): 
    print(msg) 
    cur = self.head 
    while cur != None: 
     print("%d" %cur.data, end="") 
     if cur.next != None: 
      print("->", end="") 
     else: 
      print("") 
     cur = cur.next 

    def is_palindrome(self): 
    res, ptr = rec_palindrome(self.head, self.head) 
    if res : 
     print("The input list is NOT palindrome") 
    else: 
     print("The input list is palindrome") 


if __name__ == "__main__": 
    print("Pyhton program to check if the input list is palindrome or not") 
    N = int(input("How many elements?")) 
    llist = LinkedList() 
    for i in range(N): 
    val = int(input("Enter the element of node %d" %(i+1))) 
    llist.append(Node(val)) 
    llist.display("Input Linked List") 
    llist.is_palindrome() 

example output: 
pyhton program to check if the input list is palindrome or not 
How many elements?7 
Enter the element of node 112 
Enter the element of node 245 
Enter the element of node 389 
Enter the element of node 47 
Enter the element of node 589 
Enter the element of node 645 
Enter the element of node 712 
Input Linked List 
    12->45->89->7->89->45->12 
The input list is palindrome 

Answer 14

我使用堆棧的字符存儲，直到列表的中間點。然後，我檢查列表後半部分中的字符與堆棧頂部的字符。時間：O（n）的空間：O（N/2）

SinglyLinkedList.prototype.isPalindrome = function() { 
    var slow = this.head; 
    var fast = this.head; 
    var stack = []; 

    if(!slow) return false; 

    while(fast.next != null && fast.next.next != null) { 
     fast = fast.next.next 
     stack.push(slow.element); 
     slow = slow.next; 
    } 

    // check for odd or even list. if even, push the current slow to the stack. 
    if(fast.next != null) { 
     stack.push(slow.element); 
    } 

    while(slow.next) { 
     slow = slow.next; 
     if(stack.pop() !== slow.element) return false; 
    } 

    return true; 
} 

Answer 15

void reverse(Node** head_ref) 
{ 
    struct Node* prev = NULL; 
    struct Node* current = *head_ref; 
    struct Node* next; 
    while (current != NULL) 
    { 
     next = current->next; 
     current->next = prev; 
     prev = current; 
     current = next; 
    } 
    *head_ref = prev; 
} 

bool compair(Node *t,Node *t2){ 
    Node *p = t; 
    Node *q = t2; 
    while(q && q){ 
     if(p->data==q->data){ 
      p = p->next; 
      q = q->next; 
     } 
     else{ 
      return false; 
     } 
    } 
    if(p==NULL && q==NULL){ 
     return true; 
    } 
    return false; 
} 
bool isPalindrome(Node *head) 
{ 
    //Your code here 
    if(head==NULL)return true; 
    Node *slow = head; 
    Node *fast = head; 
    Node *prevSlow; 
    Node *middle = NULL; 
    bool ans=true; 
    if(head && head->next){ 
     while(slow && fast&&fast->next){ 
      prevSlow = slow; 
      slow = slow->next; 
      fast = fast->next->next; 
     } 
     if(fast!=NULL){ 
      middle = slow; 
      slow = slow->next; 
     } 
     prevSlow->next=NULL; 
     Node *secondHalf = slow; 
     reverse(&secondHalf); 
     ans = compair(head,secondHalf); 
     if(middle!=NULL){ 
      prevSlow->next = middle; 
      middle->next = secondHalf; 
     } 
     else{ 
      prevSlow->next = secondHalf; 
     } 
    } 
    return ans; 

} 

Answer 16

遞歸算法的實現。目的只是利用自然遞歸堆棧。

void solve(Node *curr, Node **head, bool *ans) { 
    if (!curr) return; 
    solve(curr->next, head, ans); 
    if ((*head)->val != curr->val) 
    *ans = false; 
    (*head) = (*head)->next; 
} 

bool is_palindrome(Node *l) { 
    bool ans = true; 
    solve(l, &l, &ans); 
    return ans; 
} 

Answer 17

橫貫整個前半部分，並將其放入堆棧並遍歷剩下的一半並同時從堆棧彈出並檢查兩者是否相同。如果兩者都是相同的，那麼它是迴文，否則不是。