연쇄표 면접문제(一)

public class MySingleLinkedlmpl {
    class Node{
        public int getData() {
            return data;
        }
        private int data;
        public Node next;
        public Node(int data){
            this.data=data;
            this.next=null;
        }
    }// 
    private Node head;
    public MySingleLinkedlmpl(){
        this.head=null;
    }
    public Node reverseList(){
        Node reverseHead=null;// 
        Node prev=null;//cur 
        Node cur=this.head;//cur 
        while (cur!=null){
            Node curNext=cur.next;
            if(curNext==null){
                reverseHead=cur;
            }
            cur.next=prev;
            prev=cur;
            cur=curNext;
        }
        return reverseHead;
    }
    }

public class MySingleLinkedlmpl {
    class Node{
        public int getData() {
            return data;
        }
        private int data;
        public Node next;
        public Node(int data){
            this.data=data;
            this.next=null;
        }
    }// 
    private Node head;
    public MySingleLinkedlmpl(){
        this.head=null;
    }
    public Node detectCycle(){
        Node fast=this.head;
        Node slow=this.head;
        while (fast!=null && fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow ){
                break;
            }
        }
        // 
        if(fast==null || fast.next.next==null){
            return null;
        }
        // slow ， fast 
        slow=this.head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    }

public class MySingleLinkedlmpl {
    class Node{
        public int getData() {
            return data;
        }
        private int data;
        public Node next;
        public Node(int data){
            this.data=data;
            this.next=null;
        }
    }// 
    private Node head;
    public MySingleLinkedlmpl(){
        this.head=null;
    }
    public boolean hasCycle(){
        Node fast=this.head;
        Node slow=this.head;
        while (fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
    }

public class MySingleLinkedlmpl {
    class Node{
        public int getData() {
            return data;
        }
        private int data;
        public Node next;
        public Node(int data){
            this.data=data;
            this.next=null;
        }
    }// 
    private Node head;
    public MySingleLinkedlmpl(){
        this.head=null;
    }
    public boolean chkPalindrome(){
        Node fast=this.head;
        Node slow=this.head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //slow 
        Node p=slow.next;
        Node pNext=p.next;
        while (p!=null){
            p.next=slow;
            slow=p;
            p=p.next;
            if(p!=null){
                pNext=p.next;
            }
        }
        // 
        while (this.head!=slow){
            if(this.head.data!=slow.data){
                return false;
            }
            if(this.head.next==slow){
                return true;
            }
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
    }

public class MySingleLinkedlmpl {
    class Node{
        public int getData() {
            return data;
        }
        private int data;
        public Node next;
        public Node(int data){
            this.data=data;
            this.next=null;
        }
    }// 
    private Node head;
    public MySingleLinkedlmpl(){
        this.head=null;
    }
    public Node deleteDuplication(){
        Node node=new Node(-1);
        Node cur=this.head;
        Node tmpHead=node;
        while (cur!=null){
            if(cur.next!=null&&cur.data==cur.next.data){
                while (cur.next!=null&&cur.data==cur.next.data){
                    cur=cur.next;
                }
                cur=cur.next;
                //cur 
                tmpHead.next=cur;
            }else{
                // ， 
             tmpHead.next=cur;
             tmpHead=cur;
             cur=cur.next;
            }
        }
        return node.next;
    }
    }