链表之单向链表判断回文

柔情只为你懂 2021-09-18 04:28 372阅读 0赞

思考题：  
如何判断一个字符串是否是回文字符串的问题，我想你应该听过，我们今天的题目就是基于这个问题的改造版本。如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？你有什么好的解决思路呢？相应的时间空间复杂度又是多少呢？

1.  使用快慢指针定位中间节点
2.  从开始对前半部分到中间节点逆序
3.  前后半部分比较，判断是否为回文

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70]  
如图所示：  
采用快慢指针 slow、fast  
慢指针每次走一步： slow = slow.next  
快指针每次都两步：fast = fast.next.next  
通过循环表里周到链表的重点，截至条件就是 fast != null && fast.next != null

然后在循环的过程中，将前半部分链表翻转。但是要注意链表中点的放置位置  
当 fast 不是 null 的时候，表示为奇数，这个时候后半部分的slow = slow.next  
也就是：  
奇数：U->H (前半部分) U->H（后半部分）  
偶数：A->U->H (前半部分) A->U->H（后半部分）

代码实现如下：

**ListNode**

public class ListNode<T> {
    
        public ListNode next;
    
        public T value;
    
        @Override
        public String toString() {
            return "ListNode [next=" + next + ", value=" + value + "]";
        }
    
        public ListNode(ListNode next, T value) {
            this.next = next;
            this.value = value;
        }
    
    }

算法实现：

public class Palindrome {
    
    	public static boolean isPalindrome(ListNode<String> node) {
    		if( node == null || node.next == null) {
    			return true;
    		}
            ListNode<String> slow = node;// 慢指针
            ListNode<String> fast = node;// 快指针
            ListNode<String> pre = null; // 前一个节点
    		while(fast != null && fast.next != null) {
                // 快指针继续走 直到找到中点
    			fast = fast.next.next;
    			// 慢指针翻转
    			ListNode<String> next = slow.next; // 保存下一个节点指针，防止断掉
    			slow.next = pre; // 将当前指针指向前一个对象
    			pre = slow;  // 当前指针 变成 前一个对象
    			// 继续遍历
    			slow = next;
    		}
    		// 判断奇偶
    		if(fast != null) {
    			slow = slow.next;
    		}
    		while(slow != null) {
    			if(!slow.value.equals(pre.value)) {
    				return false;
    			}
    		}
    		return true;
    	}
    
    }

可以看到没有使用额外的空间，所以空间复杂度为O(1)  
一次遍历便可以实现，所以时间复杂度为O(n)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70]: /images/20210918/fbebcc1877d24b20a23587eedccd14f6.png