LeetCode(回文链表)

拼搏现实的明天。 2022-02-03 12:23 172阅读 0赞

**题目：**

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2  
输出: false  
示例 2:

输入: 1->2->2->1  
输出: true

代码1

//获取链表的长度
        int length = 0;
        ListNode node = head;
        if(null == head.next){
            length = 1;
        }else{
            do{
                length++;
            }while(null != (node = node.next));
        }
    
        Stack<Integer> stack = new Stack<>();
        //如果ListNode的长度为单数
        if(1 == length % 2){
            //入栈
            for(int i = 0, j = length / 2; i < j; i++){
                stack.push(head.val);
                head = head.next;
            }
    
            head = head.next;
    
            //出栈
            for(int i = length / 2 + 1, j = length; i < j; i++){
                if(head.val != stack.pop()){
                    return false;
                }
                head = head.next;
            }
        //如果ListNode的长度为双数
        }else{
            //入栈
            for(int i = 0, j = length / 2; i < j; i++){
                stack.push(head.val);
                head = head.next;
            }
            //出栈
            for(int i = length / 2 + 1, j = length; i <= j; i++){
                if(head.val != stack.pop()){
                    return false;
                }
                head = head.next;
            }
        }
    
        return true;
    }

代码2

class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) return true; // 只有一个节点肯定是true
            ListNode fast = head;
            ListNode slow = head;
            ListNode temp = null;
            while (fast != null){
                /**
                 * 1.快速找到中间的节点
                 * 2.将慢指针指向的前半部分翻转
                 * 3.从中间开始向左右两边遍历比较
                 */
                if (fast.next != null){ // 偶数个节点
                    slow = slow.next;
                    fast = fast.next.next;
                    // 遍历时顺便翻转前半部分
                    head.next = temp; // 翻转代码
                    temp = head;
                    head = slow;
                } else { // 奇数个节点
                    
                    slow = slow.next;
                    // 遍历时顺便翻转前半部分
                    head.next = temp; // 翻转代码
                    head = slow;
                    break;
                }
    
            }
            while (temp != null){
                if (temp.val != head.val) return false;
                temp = temp.next;
                head = head.next;
            }
            return true;
        }
    }