leetcode热题100学习计划-链表-回文链表

leetcode 234 回文链表

思路

1.在不改变原有链表结构前提下，可以用快慢指针配合栈。慢指针走一步，快指针走两步，快指针走到末尾时，慢指针走到中间，慢指针继续往后走并且把结点保存到栈中，走到末尾。堆栈一边出栈一边和链表起始进行比较。

2.通过改变链表结构，可以用快慢指针，将一半的链表反转。然后一一比较。

代码

思路一

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow=head,fast=head;
        while(fast!=null){
            slow=slow.next;
            if(fast.next!=null){
                fast=fast.next;
            }
            fast=fast.next;
        }
        Stack stack=new Stack();
        while(slow!=null){
            stack.push(slow);
            slow=slow.next;
        }
        slow=head;
        while((!stack.empty())&&(slow!=null)){
            if(stack.pop().val!=slow.val){
                return false;
            }
            
            slow=slow.next;
        }
        return true;
    }
}

思路二

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow=head,fast=head;
        while(fast!=null){
            slow=slow.next;
            if(fast.next!=null){
                fast=fast.next;
            }
            fast=fast.next;
        }
        fast=reverseList(slow);
        slow=head;
        
        while(fast!=null){
            if(fast.val!=slow.val){
                return false;
            }
            fast=fast.next;
            slow=slow.next;
        }
        return true;
    }
    public ListNode reverseList(ListNode head) {
        //使用头插法
        
        //虚拟节点，
        ListNode dummynode=new ListNode(0);
        dummynode.next=null;
        ListNode curr = head;
        ListNode q=null;
        while (curr != null) {
            //把第一个结点保存一下
            q=dummynode.next;
            //把当前结点接在虚拟节点后面
            dummynode.next=curr;
            //当前结点移到下一个结点
            curr=curr.next;
            //把之前的拼回去
            dummynode.next.next=q;
        }
        return dummynode.next;
    }
}