单链接列表是回文是否

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

横贯整个前半部分，并将其放入堆栈并遍历剩下的一半并同时从堆栈弹出并检查两者是否相同。如果两者都是相同的，那么它是回文，否则不是。