LinkedListでの回文をチェックするには - linked linkedListとReverse LinkedListを比較してください。

Question

public class CheckPalindromeLL { 

    public static void main(String args[]) 
    { 
     Link head=null; 

     Link l1=createLinkList1(head); 
     Link l2=l1; 
     System.out.println("first linklist"); 
     display(l1); 

     System.out.println("reveresed linklist"); 
     Link rev=reverse(l1); 
     Link rev2=rev; 
     display(rev2); 
     System.out.println("IS PALINDROME"); 
     compare(l1,rev); 
    } 

    private static Link reverse(Link l11) { 
     Link l12=l11; 
     // TODO Auto-generated method stub 
     Link nextp; 
     Link curr=l12; 
     Link prevp=null; 
     while(curr!=null) 
     { 
      nextp=curr.next; 
      curr.next=prevp; 
      prevp=curr; 
      curr=nextp; 
     } 

     return prevp; 
    } 

    private static boolean compare(Link d1, Link d2) { 

     boolean flag=true; 
     while((d1!=null) && (d2!=null)&& flag) 
     { 
      if(d1.num!=d2.num) 
      { System.out.println("not same "); 
       flag=false; 
       break; 
      } 
      else 
      { 
       System.out.println("list:"+d1.num); 
       System.out.println("rev:"+d2.num); 
       System.out.println(" same"); 
       d1=d1.next; 
       d2=d2.next; 
      } 
     } 

     System.out.println("printing flag"+flag); 
     return flag; 
    } 

    private static Link createLinkList1(Link head) { 
     // TODO Auto-generated method stub 
     Link firstlink=head; 
     Link newLink = null; 

     Scanner reader = new Scanner(System.in); 
     System.out.println("Enter a number: "); 
     int x[]={1,2,3,1}; 
     for(int i=0;i<x.length;i++) 
     { 
      newLink=new Link(x[i]); 
      newLink.next=firstlink; 
      firstlink=newLink; 
     } 
     head= firstlink; 
     return newLink; 
    } 

    public static void display(Link start) 
    { 
     Link s1=start; 
     while(s1!=null) 
     { 
      System.out.println(s1.num); 
      s1=s1.next; 
     } 
    } 
} 

linkedlistを比較し、linkedlistの逆が、第2 element.Itを比較することはできませんだけで、オリジナルの最初の要素をチェックして、linkedlistを逆にし、最初の要素に基づいて答えを与えるonly.Am私は何かが足りません？

Answer 1

ここでは、あなたのリスト（単数形）が各ステップでどのように見えるかをASCIIアートで描いています。余計な文と印刷文を省いた：

Link l1=createLinkList1(head); 

     l1-+ 
      | 
      V 
      1 -> 2 -> 3 -> 1 -> null 

Link rev=reverse(l1); 

    rev------------------+ 
         | 
     l1-+    | 
      |    | 
      V    V 
    null <- 1 <- 2 <- 3 <- 1 

compare(l1,rev); 

あなたは1つのリストと1つのノードセットを2つではなく作成します。 reverse()の場合はポインタを再配置しますが、l1は最初の要素であったものを指し示していますが、最後は最後の要素です。

Answer 2

元のリストの完全なコピーを逆順に作成する必要があります。あなたが（ケースのためにあなたが...あなたの実装を適応させるために喜んでいる）二重リンクリストを持っている場合は、簡単にすることなく、回文かどうかを確認することができます

private static Link reverse(Link l) 
{ 
    Link result = null; 
    while(l != null) 
    { 
     Link ll = new Link(l.value); 
     ll.next = result; 
     result = ll; 
     l = l.next; 
    } 
    return result; 
} 

ただ、ほかのように：これは、トリックを行う必要がありますリストを複製せずに回文を確認する（再帰的）：：ただギミック

private static boolean isPalindrome(Link head, Link tail) 
{ 
    if(head == null) 
    { 
     return true; // arguable, if empty list is palindrome or not... 
    } 
    while(head != tail) 
    { 
     if(head.value != tail.value) 
     { 
      return false; 
     } 
     head = head.next; 
     if(head == tail) // need this for even number of list elements 
     { 
      break; 
     } 
     tail = tail.previous; 
    } 
    return true; 
} 

EDIT ：

逆コピーを作成します3210

private static boolean isPalindrome(Link head) 
{ 
    return head == null ? true : isPalindrome(new Link[] { head }, head); 
} 
private static boolean isPalindrome(Link[] head, Link tail) 
{ 
    if(tail.next != null) 
    { 
     if(!isPalindrome(head, tail.next)) 
     { 
      return false; 
     } 
     head[0] = head[0].next; 
    } 
    return head[0].value == tail.value; 
}