526互联

回文链表

发布时间 2024-01-03 11:06:52作者: Noule

链表

回文问题

思路来源

一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到

笔记内容

  • 问题描述

    给定一个单向链表，判断是不是回文。

  • 算法思路

    首先遍历链表获取链表长度，然后将指针移到链表中点，对后半部分的链表进行倒序的连接修改。最后移动首尾指针，进行回文判断。

  • 代码实现

    /**
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
*/

public static boolean palindrome(ListNode node){
        if(node.next == null){
            return true;
        }
        if(node.next.next == null){
            return node.val == node.next.val ? true : false ;
        }

        int count = length(node,null)/2;
        ListNode head = node;
        while (count > 0){
            head = head.next;
            count--;
        }
        ListNode cur = head;
        head =head.next;
        cur.next = null;
        while (head != null){
                ListNode next = head;
                head = head.next;
                next.next = cur;
                cur = next;
        }
        head = cur;
        while (node != null && head != null){
            if(node.val != head.val){
                return false;
            }
            node = node.next;
            head = head.next;
        }
        return true;
    }

    public static int length(ListNode head,ListNode end){
        int count = 0;
        if(end == null){
            while (head != null){
                count++;
                head = head.next;
            }
        }else {
            while (head != end){
                count++;
                head = head.next;
            }
        }
        return count;
    }