给定两个字符串，表示为链表（每个字符都是链表中的一个节点）。编写一个类似于strcmp（）的函数compare（），即，如果两个字符串相同，则返回0；如果第一个链表按字典顺序更大，则返回1；如果第二个字符串按字典顺序更大，则返回-1。
null
例如：
输入： 列表1=g->e->e->k->s->a 列表2=g->e->e->k->s->b 输出： -1 说明： “geeksb”在词汇上比“geeksa”大。
输入： 列表1=g->e->e->k->s->a 列表2=g->e->e->k->s 输出： 1. 说明： “极客”比“极客”更老套。
输入： 列表1=g->e->e->k->s 列表2=g->e->e->k->s 输出： 0 说明： 这两个字符串都是“极客”。
天真的方法： 遍历链表并形成字符串。现在比较两个字符串，检查两个字符串是否相同。
时间复杂性： O（N+M），其中N和M是链表的长度。 辅助空间： O（N+M）
有效方法： 一个有效的方法是使用 双指针 算法。按照以下步骤操作：
- 创造 两点 并指向 链表的开始 .
- 遍历两个列表。如果字符相同，则继续遍历并递增两个指针。
- 如果有 不匹配 :
- 如果字符位于 列表1在词典编纂上更大 打印1并停止迭代。
- 如果字符位于 清单2在词典编纂上更大 打印-1并停止迭代。
- 如果遍历到达 列表之一的末尾 :
- 如果 另一端 列表也已到达 两个字符串都是一样的 .
- 除此之外，另一个是词典中更大的一个。
以下是上述方法的实施情况。
C++
// C++ program to compare two strings // represented as linked lists #include<bits/stdc++.h> using namespace std; // Linked list Node structure struct Node { char c; struct Node *next; }; // Function to create newNode in a linkedlist Node* newNode( char c) { Node *temp = new Node; temp->c = c; temp->next = NULL; return temp; }; int compare(Node *list1, Node *list2) { // Traverse both lists. Stop when // either end of a linked list is reached // or current characters don't match while (list1 && list2 && list1->c == list2->c) { list1 = list1->next; list2 = list2->next; } // If both lists are not empty, // compare mismatching characters if (list1 && list2) return (list1->c > list2->c)? 1: -1; // If either of the two lists // has reached end if (list1 && !list2) return 1; if (list2 && !list1) return -1; // If none of the above conditions is true, // both lists have reached end return 0; } // Driver code int main() { Node *list1 = newNode( 'g' ); list1->next = newNode( 'e' ); list1->next->next = newNode( 'e' ); list1->next->next->next = newNode( 'k' ); list1->next->next->next->next = newNode( 's' ); list1->next->next->next->next->next = newNode( 'b' ); Node *list2 = newNode( 'g' ); list2->next = newNode( 'e' ); list2->next->next = newNode( 'e' ); list2->next->next->next = newNode( 'k' ); list2->next->next->next->next = newNode( 's' ); list2->next->next->next->next->next = newNode( 'a' ); cout << compare(list1, list2); return 0; } |
JAVA
// Java program to compare two strings represented as a linked list // Linked List Class class LinkedList { Node head; // head of list static Node a, b; /* Node Class */ static class Node { char data; Node next; // Constructor to create a new node Node( char d) { data = d; next = null ; } } int compare(Node node1, Node node2) { if (node1 == null && node2 == null ) { return 1 ; } while (node1 != null && node2 != null && node1.data == node2.data) { node1 = node1.next; node2 = node2.next; } // if the list are different in size if (node1 != null && node2 != null ) { return (node1.data > node2.data ? 1 : - 1 ); } // if either of the list has reached end if (node1 != null && node2 == null ) { return 1 ; } if (node1 == null && node2 != null ) { return - 1 ; } return 0 ; } public static void main(String[] args) { LinkedList list = new LinkedList(); Node result = null ; list.a = new Node( 'g' ); list.a.next = new Node( 'e' ); list.a.next.next = new Node( 'e' ); list.a.next.next.next = new Node( 'k' ); list.a.next.next.next.next = new Node( 's' ); list.a.next.next.next.next.next = new Node( 'b' ); list.b = new Node( 'g' ); list.b.next = new Node( 'e' ); list.b.next.next = new Node( 'e' ); list.b.next.next.next = new Node( 'k' ); list.b.next.next.next.next = new Node( 's' ); list.b.next.next.next.next.next = new Node( 'a' ); int value; value = list.compare(a, b); System.out.println(value); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python program to compare two strings represented as # linked lists # A linked list node structure class Node: # Constructor to create a new node def __init__( self , key): self .c = key ; self . next = None def compare(list1, list2): # Traverse both lists. Stop when either end of linked # list is reached or current characters don't match while (list1 and list2 and list1.c = = list2.c): list1 = list1. next list2 = list2. next # If both lists are not empty, compare mismatching # characters if (list1 and list2): return 1 if list1.c > list2.c else - 1 # If either of the two lists has reached end if (list1 and not list2): return 1 if (list2 and not list1): return - 1 return 0 # Driver program list1 = Node( 'g' ) list1. next = Node( 'e' ) list1. next . next = Node( 'e' ) list1. next . next . next = Node( 'k' ) list1. next . next . next . next = Node( 's' ) list1. next . next . next . next . next = Node( 'b' ) list2 = Node( 'g' ) list2. next = Node( 'e' ) list2. next . next = Node( 'e' ) list2. next . next . next = Node( 'k' ) list2. next . next . next . next = Node( 's' ) list2. next . next . next . next . next = Node( 'a' ) print (compare(list1, list2)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to compare two // strings represented as a linked list using System; // Linked List Class public class LinkedList { public Node head; // head of list public Node a, b; /* Node Class */ public class Node { public char data; public Node next; // Constructor to create a new node public Node( char d) { data = d; next = null ; } } int compare(Node node1, Node node2) { if (node1 == null && node2 == null ) { return 1; } while (node1 != null && node2 != null && node1.data == node2.data) { node1 = node1.next; node2 = node2.next; } // if the list are different in size if (node1 != null && node2 != null ) { return (node1.data > node2.data ? 1 : -1); } // if either of the list has reached end if (node1 != null && node2 == null ) { return 1; } if (node1 == null && node2 != null ) { return -1; } return 0; } // Driver code public static void Main(String[] args) { LinkedList list = new LinkedList(); list.a = new Node( 'g' ); list.a.next = new Node( 'e' ); list.a.next.next = new Node( 'e' ); list.a.next.next.next = new Node( 'k' ); list.a.next.next.next.next = new Node( 's' ); list.a.next.next.next.next.next = new Node( 'b' ); list.b = new Node( 'g' ); list.b.next = new Node( 'e' ); list.b.next.next = new Node( 'e' ); list.b.next.next.next = new Node( 'k' ); list.b.next.next.next.next = new Node( 's' ); list.b.next.next.next.next.next = new Node( 'a' ); int value; value = list.compare(list.a, list.b); Console.WriteLine(value); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript program to compare two // strings represented as a linked list // Linked List Class var head; // head of list var a, b; /* Node Class */ class Node { // Constructor to create a new node constructor(d) { this .data = d; this .next = null ; } } function compare(node1, node2) { if (node1 == null && node2 == null ) { return 1; } while (node1 != null && node2 != null && node1.data == node2.data) { node1 = node1.next; node2 = node2.next; } // if the list are different in size if (node1 != null && node2 != null ) { return (node1.data > node2.data ? 1 : -1); } // if either of the list has reached end if (node1 != null && node2 == null ) { return 1; } if (node1 == null && node2 != null ) { return -1; } return 0; } var result = null ; a = new Node( 'g' ); a.next = new Node( 'e' ); a.next.next = new Node( 'e' ); a.next.next.next = new Node( 'k' ); a.next.next.next.next = new Node( 's' ); a.next.next.next.next.next = new Node( 'b' ); b = new Node( 'g' ); b.next = new Node( 'e' ); b.next.next = new Node( 'e' ); b.next.next.next = new Node( 'k' ); b.next.next.next.next = new Node( 's' ); b.next.next.next.next.next = new Node( 'a' ); var value; value = compare(a, b); document.write(value); // This code contributed by gauravrajput1 </script> |
输出
1
时间复杂性： O（N+M） 辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
