leetcode 234. 回文链表的两种解法

刺骨的言语ヽ痛彻心扉 2022-03-10 12:50 137阅读 0赞

*  题目描述
    
        请判断一个链表是否为回文链表。
        
        示例 1:
        
        输入: 1->2
        输出: false
        示例 2:
        
        输入: 1->2->2->1
        输出: true
 *  基于栈实现：时间复杂度为O(n)，空间复杂度为O(n)，如下：
    
        /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
        class Solution { 
            public boolean isPalindrome(ListNode head) { 
                if (head == null || (head != null && head.next == null)) { 
                    return true;
                }
                // 获取链表长度
                int len = 0;
                ListNode tempHead = head;
                while (tempHead != null) { 
                    len++;
                    tempHead = tempHead.next;
                }
        
        		// 回文前半部分的尾结点下标
                int preHalfEndIndex = len % 2 == 0 ? (len-1)/2 : (len/2)-1;
                Stack<Integer> stack = new Stack();
                int index = 0;
                
                // 往前迭代直到head指向回文后半部分的头结点
                while (index <= preHalfEndIndex) { 
                    stack.push(head.val);
                    index++;
                    head = head.next;
                }
                // 如果是奇数长度，则需要跳过中间结点
                if (len % 2 != 0 && head.next != null) { 
                    head = head.next;
                }
                
                // 从后半部分头结点遍历，同时出栈，如果存在不相同的则说明不是回文。
                while(head != null) { 
                    if (stack.pop() != head.val) { 
                        return false;
                    }
                    head = head.next;
                }  
                return true;
            }
        }
 *  更进一步优化，实现时间复杂度为O(n)，空间复杂度为O(1)，主要是对回文后半部分进行链表反转，如下：
    
        /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
        class Solution { 
            public boolean isPalindrome(ListNode head) { 
                if (head == null || (head != null && head.next == null)) { 
                    return true;
                }
                
                // 获取链表长度
                int len = 0;
                ListNode tempHead = head;
                while (tempHead != null) { 
                    len++;
                    tempHead = tempHead.next;
                }
                
                // 获取回文链表的前半部分的最后一个下标
                int preHalfEndIndex = len % 2 == 0 ? (len-1)/2 : (len/2)-1;
                
                // temp2Head为回文链表的后半部分的头结点
                int index = 0;
                ListNode temp2Head = head;
                while (index <= preHalfEndIndex) { 
                    temp2Head = temp2Head.next;
                    index++;
                }
                if (len % 2 != 0 && temp2Head.next != null) { 
                    temp2Head = temp2Head.next;
                }
                
                // 反转后部分链表
                ListNode tail = chainReverse(temp2Head);
                
                // 前半部分从head开始，后半部分从tail开始
                while (head != null && tail != null) { 
                    if (head.val != tail.val) { 
                        return false;
                    }
                    head = head.next;
                    tail = tail.next;
                }
                
                return true;
            }
            
            // 反转链表
            private ListNode chainReverse(ListNode head) { 
                if (head == null || head.next == null) { 
                    return head;
                }
                
                ListNode backward = head;
                ListNode forward = head.next;
                head.next = null;
                
                while (forward != null) { 
                    head = forward;
                    forward = forward.next;
                    head.next = backward;
                    backward = head;
                }
                
                return head;
            }
        }