Leetcode 回文链表

Day 12 第一题

用数组存储链表的数值，在检测是否是回文数组，数组长度不可变，所以用list

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();

        while(head != null){
            list.add(head.val) ;
            head = head.next;
        }

        int n = list.size();
        for(int i=0;i<n;i++){
            if(list.get(i)!=list.get(n-1-i)){
                return false;
            }
        }

        return true;
    }
}

进阶：需要算法的时间复杂度\(\mathcal{O}(1)\)，空间复杂度为\(\mathcal{O}(n)\)。使用快慢指针找到中间节点的位置，若数组为偶数，则快指针为空，慢指针指向\(n/2+1\)；若数组数为奇数，则快指针不为空，慢指针指向\((n+1)/2\)，难题在于反转后半部分链表；

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null){
            return true;
        }

        ListNode endOfFirst = endOfFirst(head);
        ListNode secondStart = reverse(endOfFirst.next);
        System.out.println(secondStart.val);

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

        }

        reverse(endOfFirst.next);
        return true;
        
    }

    private ListNode endOfFirst(ListNode head){
        ListNode fast = head;
        ListNode slow = head;

        while(fast.next.next!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur.next!=null){
            // 存储当前的下一个节点信息
            ListNode temp = cur.next;
            // 将链表箭头反转
            cur.next = pre;
            // 将pre随着链表反转向前推
            pre = cur;
            // 继续滑动节点向前
            cur = temp;
        }
        return cur;
    }
}

上述代码是过不了[1,0,0]的案例的，while(fast.next.next!=null && fast.next!=null){会报错。以及反转的最后一个节点没有反转，会导致第二部分始终只有一个节点。正确reverse如下：

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            // 存储当前的下一个节点信息
            ListNode temp = cur.next;
            // 将链表箭头反转
            cur.next = pre;
            // 将pre随着链表反转向前推
            pre = cur;
            // 继续滑动节点向前
            cur = temp;
        }
        return pre;
    }

补充：linkedList新增的首尾操作的特有方法

public E getFirst() 返回链表的第一个元素；

public E getLast() 返回链表的最后一个元素；

public E removeFirst() 删除链表的第一个元素；

public E removeLast() 删除链表的最后一个元素；