[数据结构与算法]【leetcode】【初级算法】【链表5】回文链表

题目

回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true
示例 2：

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

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnv1oc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解

    回文链表
    三种方法：转为数组 、递归、快慢指针

方法一：转为数组

java解

在java中 列表分为 数组列表 和 链表

    // 数组列表底层使用数组存储 可以通过下标访问 复杂度是O（1）(注：数组列表的长度是 数组列表名.size（）)
    // 链表底层存储是一个节点存储下一个节点的位置，访问一个节点的复杂度是O（n）

数组列表的长度数组列表名.size()
数组列表 获取其中一个元素数组列表名.get(i)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {        
        // 方法一 转数组 第一步 遍历改为数组
        // 在java中 列表分为 数组列表 和 链表
        // 数组列表底层使用数组存储 可以通过下标访问 复杂度是O（1）(注：数组列表的长度是 数组列表名.size（）)
        // 链表底层存储是一个节点存储下一个节点的位置，访问一个节点的复杂度是O（n）

        // 第一步 定义数组列表
        List<Integer> vals = new ArrayList<Integer>();

        // 第二步，将列表的值复制到数组中
        ListNode currentNode = head;
        while(currentNode!=null){
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 第三步 使用双指针比较
        int front = 0;
        int back = vals.size()-1;
        while(front<back){
// if(vals.get(front)!=(vals.get(back))){  
        if(!vals.get(front).equals(vals.get(back))){
            
                return false;
            }
            front++;
            back--;
        }
        return true;       

    }
}

python解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        temp = []
        while head:
            temp.append(head.val)
            head = head.next
        return temp == temp[::-1]

方法二：递归

由下面的代码 可以知道 递归是从后往前的

function print_values_in_reverse(ListNode head)
	if head is NOT null
		print_values_in_reverse(head.next)
		print head.val

利用这个由后往前的特性，我们可以与一个从前往后的指针比较。·

java解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 方法二：递归 
    // 是利用了递归是从后往前操作的特点 所以可以从后往前比较。
    // 所以要定义一个全局变量 从前往后 递归的到的值从后往前。

    // 第一步定义全局变量
    private ListNode frontPointer;

    // 第二步 定义函数recursivelyCheck,输入参数是当前节点的next，返回是否是回文。
    private boolean recursivelyCheck(ListNode currentNode){
        if(currentNode!=null){
            // 递归
            if(!recursivelyCheck(currentNode.next)){
                return false;
            }
            // 判断当前值是不是相等
            if(currentNode.val !=  frontPointer.val){
                return false;
            }
            // 然后让指向前面的指着frontPointer指向下一个节点
            frontPointer = frontPointer.next;
        }
        return true;
    }
    public boolean isPalindrome(ListNode head) {
       frontPointer = head;
       return recursivelyCheck(head);
    }
}

python解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 定义一个从链表头开始的指针
        self.front_pointer = head
        # 定义一个返回是否是回文的函数
        def recursively_check(current_node=head):
            # 注意python第一步要判空 不然next会报错
            if current_node is not None:
                # 递归
                if not recursively_check(current_node.next):
                    return False
                if self.front_pointer.val!=current_node.val:
                    return False
                self.front_pointer = self.front_pointer.next
            return True
        return recursively_check()

方法三：快慢指针

java解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {  
    public boolean isPalindrome(ListNode head) {
        // 快慢指针
        // 判空
        // 1.找到前半部分链表的尾节点
        // 2.反转后半部分链表
        // 3.判断回文
        // 4.恢复链表
        // 5.返回结果

        // 第一步:判空
        if(head == null){
            return true;
        }

        // 第二步 找到前半部分链表的尾节点
        ListNode firstHalfEnd = endOfFirstHalf(head);
        // 第三步 反转后半部分链表
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);
        // 第四步 判断是否是回文   
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        // 遍历判断前半部分 和 反转的后半部分 的每个值是否相等
        while (result && p2!=null){
            if(p1.val != p2.val){
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }
    
    // 反转链表
    private ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        while(curr != null){
            ListNode nextTemp = curr.next;
            curr.next = pre;
            pev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    //返回后半部分的头节点
    private ListNode endOfFirstHalf(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next !=null && slow.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;

    }
}

python解

这个python代码好像不太对 后面再改改

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
         # 第一步 判空
        if head is None:
            return True
        
        # 第二步 找到前半部分链表的尾节点
        first_half_end = self.end_of_first_half(head)
        # 反转后半部分
        second_half_start = self.reverse_list(first_half_end.next)

        # 验证回文
        result = True
        first_position = head
        second_position = second_half_start
        while result and second_position is not None:
            if first_position.val != second_position.val:
                result = False
            # 判断完当前节点就让 first指针指向下一个
            first_position = first_position.next
            second_position = second_position.next
        
        # 还原链表 返回结果
        first_half_end.next = self.reverse_list(second_half_start)
        return result
    

    # 定义一个 返回链表中间节点的函数
    def end_of_first_half(self,head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow


    # 定义一个反转链表的函数,传入链表头节点 传出链表头节点
    def reverse_list(self,head):
        previous = None
        current = head
        while current.next is not None :
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous