学步园

We say two linked-lists are equal if they have the same number of elements, and the elements themselves are the same. Furthermore elements' order are not significant.

If compared linked-lists are not sorted, the straightforward approach to compare two linked-lists can be achieved in following way:
1)Define a method to determine whether a linked-list is a subset of the other. This can be achieved through enumerating every items in a list and determine whether they exist in the other list.
2)If a list is a subset of the other one, and vice versa, we can say that the two linked-lists are equal.

If compared linked-lists are sorted, comparing linked-lists become easier. I write the following program to sort linked-lists firstly, and then compare them. The sort algorithms can be categorized as inserting-sort.

import java.util.Random;</p> <p>class Node {<br /> int value;<br /> Node next;<br /> Node(int v){<br /> value=v;<br /> next =null;<br /> }<br /> Node(){<br /> this(0);<br /> }<br /> }</p> <p>class LinkListHandle {<br /> static boolean equals(Node head1,Node head2){<br /> while(head1!=null && head2!=null){<br /> if(head1.value!=head2.value){<br /> return false;<br /> }<br /> head1=head1.next;<br /> head2=head2.next;<br /> }<br /> if(head1==head2){<br /> return true;<br /> }else{<br /> return false;<br /> }<br /> }<br /> static Node clone(Node head){<br /> if(head==null) return null;<br /> Node first=new Node(head.value);<br /> Node remaining=clone(head.next);<br /> first.next=remaining;<br /> return first;<br /> }<br /> static Node seqInsert(Node head, Node elem){<br /> elem.next=head;<br /> return elem;<br /> }<br /> static Node sortInsert(Node head, Node elem){<br /> Node cur=head;<br /> Node prev=null;<br /> while(cur!=null && elem.value>cur.value){<br /> prev=cur;<br /> cur=cur.next;<br /> }<br /> //insert to a empty list<br /> if(cur==null && prev==null) {<br /> elem.next=null;<br /> return elem;<br /> }<br /> //insert at tail of the list<br /> if(cur==null && prev!=null) {<br /> elem.next=null;<br /> prev.next=elem;<br /> return head;<br /> }<br /> //insert at head of the list<br /> if(cur!=null && prev==null){<br /> elem.next=head;<br /> return elem;<br /> }<br /> //insert at middle of the list<br /> if(cur!=null && prev!=null){<br /> prev.next=elem;<br /> elem.next=cur;<br /> return head;<br /> }<br /> //should not reach here<br /> return null;<br /> }</p> <p> static Node insertSort(Node head){<br /> if(head==null) return head;<br /> Node newHead=null;<br /> Node next=null;</p> <p> while(head!=null){<br /> //must remember next elem here, because sortInsert may change head's next field<br /> next=head.next;<br /> newHead=sortInsert(newHead,head);<br /> head=next;<br /> }<br /> return newHead;<br /> }</p> <p> static void printLinkList(Node head){<br /> System.out.print('[');<br /> Node prev=null;<br /> Node cur=head;<br /> while(cur!=null){<br /> if(prev!=null) {<br /> System.out.print(prev.value);<br /> System.out.print(',');<br /> }<br /> prev=cur;<br /> cur=cur.next;<br /> }<br /> if(cur==null && prev!=null){<br /> System.out.print(prev.value);<br /> }<br /> System.out.println(']');<br /> }<br /> }</p> <p>public class JavaLearn {</p> <p> public static void main(String[] args) {</p> <p> // TODO, add your application code<br /> Random rnd=new Random();<br /> Node head1=null;<br /> Node head2=null;<br /> for(int i=0;i<10;i++){<br /> head1=LinkListHandle.seqInsert(head1,new Node(rnd.nextInt() % 100));<br /> }</p> <p> head2=LinkListHandle.clone(head1);<br /> System.out.println("head1");<br /> LinkListHandle.printLinkList(head1);<br /> System.out.println("head2");<br /> LinkListHandle.printLinkList(head2);</p> <p> head2=LinkListHandle.insertSort(head2);</p> <p> System.out.println("head1");<br /> LinkListHandle.printLinkList(head1);<br /> System.out.println("head2 sort");<br /> LinkListHandle.printLinkList(head2);</p> <p> head1=LinkListHandle.insertSort(head1);</p> <p> System.out.println("head1 sort");<br /> LinkListHandle.printLinkList(head1);<br /> System.out.println("head2 sort");<br /> LinkListHandle.printLinkList(head2);</p> <p> if(LinkListHandle.equals(head1,head2)){<br /> System.out.println("they are equal");<br /> }else{<br /> System.out.println("they are not equal");<br /> }<br /> }<br /> }<br />

//running output<br /> head1<br /> [-50,-92,35,67,-94,-53,-56,50,-38,-4]<br /> head2<br /> [-50,-92,35,67,-94,-53,-56,50,-38,-4]<br /> head1<br /> [-50,-92,35,67,-94,-53,-56,50,-38,-4]<br /> head2 sort<br /> [-94,-92,-56,-53,-50,-38,-4,35,50,67]<br /> head1 sort<br /> [-94,-92,-56,-53,-50,-38,-4,35,50,67]<br /> head2 sort<br /> [-94,-92,-56,-53,-50,-38,-4,35,50,67]<br /> they are equal