LetCode

제목:
하나의 체인 테이블이 회문 체인 테이블인지 아닌지를 판단하십시오.
예1:
입력: 1->2 출력:false 예2:
입력: 1->2->2->1 출력:true
코드 1
//       
    int length = 0;
    ListNode node = head;
    if(null == head.next){
        length = 1;
    }else{
        do{
            length++;
        }while(null != (node = node.next));
    }

    Stack stack = new Stack<>();
    //  ListNode      
    if(1 == length % 2){
        //  
        for(int i = 0, j = length / 2; i < j; i++){
            stack.push(head.val);
            head = head.next;
        }

        head = head.next;

        //  
        for(int i = length / 2 + 1, j = length; i < j; i++){
            if(head.val != stack.pop()){
                return false;
            }
            head = head.next;
        }
    //  ListNode      
    }else{
        //  
        for(int i = 0, j = length / 2; i < j; i++){
            stack.push(head.val);
            head = head.next;
        }
        //  
        for(int i = length / 2 + 1, j = length; i <= j; i++){
            if(head.val != stack.pop()){
                return false;
            }
            head = head.next;
        }
    }

    return true;
}

코드 2
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true; //          true
        ListNode fast = head;
        ListNode slow = head;
        ListNode temp = null;
        while (fast != null){
            /**
             * 1.         
             * 2.             
             * 3.              
             */
            if (fast.next != null){ //      
                slow = slow.next;
                fast = fast.next.next;
                //            
                head.next = temp; //     
                temp = head;
                head = slow;
            } else { //      
                
                slow = slow.next;
                //            
                head.next = temp; //     
                head = slow;
                break;
            }

        }
        while (temp != null){
            if (temp.val != head.val) return false;
            temp = temp.next;
            head = head.next;
        }
        return true;
    }
}

좋은 웹페이지 즐겨찾기