public class Solution {
    public boolean isPalindrome(ListNode head) {
         if(head==null||head.next==null)return true;
        ListNode newhead=head;
        int len=0;
        while(newhead!=null){
            newhead=newhead.next;
            len++;
        }
       
        int i=0;
        while(i<len/2){
            ListNode temp=head.next;
            head.next=newhead;
            newhead=head;
            head=temp;
            i++;
        }
        if(len%2==1)head=head.next;
        while(head!=null){
            if(head.val!=newhead.val)return false;
            head=head.next;
            newhead=newhead.next;
        }
        return true;
    }
}

public class Solution {
    public String largestNumber(int[] nums){
        Integer[]in=new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            in[i]=nums[i];
        }
        Arrays.sort(in,new Compare());
        StringBuilder sb = new StringBuilder();
        for (int i = nums.length - 1; i >= 0; i--) {
            sb.append(in[i]);
        }
        if(sb.charAt(0) == '0'){
            return "0";
        }
        return sb.toString();
    }

    public class Compare implements Comparator<Integer> {
        public int compare(Integer arg0, Integer arg1) {
            String s1 = arg0.toString();
            String s2 = arg1.toString() + arg1.toString();
            while (s1.length() < s2.length()) {
                s1 += s1;
            }
            while (s2.length() < s1.length()) {
                s2 += s2;
            }
            return s1.compareTo(s2);
        }

    }
}

public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int total=(C-A)*(D-B)+(G-E)*(H-F);
        return total-getIntersect(A,C,E,G)*getIntersect(B,D,F,H);
    }
    public int getIntersect(int x1,int x2, int x3, int x4){
        if(x2<x3||x1>x4)return 0;
        return Math.abs(Math.max(x1,x3)-Math.min(x2,x4));
    }
}

public class Solution {
    public List<String> summaryRanges(int[] nums) {
        int i=0;
        List<String> result=new ArrayList<String>();
        while(i<nums.length){
            int start =nums[i];
            int end=nums[i];
            while(i<nums.length-1&&nums[i]+1==nums[i+1]){
                end++;
                i++;
            }
            if(start==end){
                result.add(start+"");
            }else{
                result.add(start+"->"+end);
            }
            i++;
        }
        return result;
    }
}

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        int c;
        ListNode newhead=head;
        ListNode last=head;
        boolean needMoveHead=true;
       
        while(head!=null&&head.next!=null){
            c=0;
            while(head.next!=null&&head.val==head.next.val){            
                c++;
                head=head.next;
            }
           
            if(c>=1){
                // need to cut it
                if(needMoveHead){
                    // it's the first element, move the new head
                    newhead=head.next;
                }
                // cut it
                last.next=head.next;
               
            }else{
                // doesn't need to cut it. No need to move new head now
                needMoveHead=false;
                last=head;
            }
            head=head.next;
        }
       
        return newhead;
    }
}