剑指offer

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

输入: head = [1,2,3,3,2,1]
输出: true

输入: head = [1,2]
输出: false

链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9

package jianzhioffer;

import java.util.ArrayList;
import java.util.List;

public class offer_27 {
    public static void main(String[] args) {
        linkList list = new linkList();

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(2);
        ListNode node7 = new ListNode(1);

        list.add(node1);
        list.add(node2);
        list.add(node3);
        list.add(node4);
        list.add(node5);
        list.add(node6);
        list.add(node7);

        System.out.println(isPalindrome(node1));
    }

    public static boolean isPalindrome(ListNode head) {
        ListNode temp = head;
        List list = new ArrayList<>();
        // 把节点添加到线性表
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        int i = 0;
        int j = list.size() - 1;
        while (i < j) {
            if (list.get(i) != list.get(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode (int x) {
            val = x;
            next = null;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    
    static class linkList {
        ListNode head = new ListNode(0);
        
        public void add(ListNode node) {
            ListNode temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = node;
        }
    }
}

import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        linkList list = new linkList();

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(2);
        ListNode node7 = new ListNode(1);

        list.add(node1);
        list.add(node2);
        list.add(node3);
        list.add(node4);
        list.add(node5);
        list.add(node6);
        list.add(node7);

        System.out.println(isPalindrome(node1));
    }

    public static boolean isPalindrome(ListNode head) {
        // 寻找中间节点并把后半段链表反转
        ListNode mid = midNode(head);
        ListNode l2 = reverse(mid.next);

        boolean res = true;

        // 判断是否回文
        while (res && l2 != null) {
            if (head.val != l2.val) {
                res = false;
            }
            head = head.next;
            l2 = l2.next;
        }
        // 记得还原链表，虽然本题并没有要求还原链表，
        // 但是在实际开发中，不能因为判断是否回文就随意更改链表的结构。
        mid.next = reverse(l2);
        return res;
    }

    // 寻找中间节点
    public static ListNode midNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 反转链表
    public static ListNode reverse (ListNode head) {
        ListNode res = head;
        ListNode nextTemp = null;
        ListNode temp = null;
        while (res != null) {
            nextTemp = res.next;
            res.next = temp;
            temp = res;
            res = nextTemp;
        }
        return temp;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode (int x) {
            val = x;
            next = null;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    
    static class linkList {
        ListNode head = new ListNode(0);
        
        public void add(ListNode node) {
            ListNode temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = node;
        }
    }
}