NC96判断一个链表是否为回文结构

- 1、题目描述：

- 2、题目链接：
https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f?tpId=117&tqId=37813&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

-3、 设计思想：

详细操作流程看下图：

-4、视频讲解链接B站视频讲解

-5、代码：
c++版本:

 /**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        if(head == NULL || head->next == NULL) return true;
        ListNode* slow = head;//慢指针
        ListNode* fast = head;//快指针
        //找到中间节点
        while(fast != NULL && fast->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
        }
        //找到中间节点后让fast指针指向slow->next;
        fast = slow->next;
        slow->next = NULL;
        ListNode* newList = NULL;
        //进行后半部分的翻转
        while(fast!= NULL)
        {
            newList = fast->next;
            fast->next = slow;
            slow = fast;
            fast = newList;
        }
        newList = slow;
        fast = head;
        //判断回文
        while (fast != NULL && newList != NULL) { 
            if (fast->val != newList->val) {
                return false;
            }
            fast = fast->next; 
            newList = newList->next; 
        }
        return true;


    }
};

Java版本：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        if(head == null || head.next == null) return true;
        ListNode slow = head;//慢指针
        ListNode fast = head;//快指针
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //找到中间节点后让fast指针指向slow->next;
        fast = slow.next;
        slow.next = null;
        ListNode newList = null;
        while(fast != null){
            newList = fast.next;
            fast.next = slow;
            slow = fast;
            fast = newList;
        }
        newList = slow;
        fast = head;
        //判断回文
        while (fast != null && newList != null) { 
            if (fast.val != newList.val) {
                return false;
            }
            fast = fast.next; 
            newList = newList.next; 
        }
        return true;

    }
}

Python版本:

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    def isPail(self , head ):
        # write code here
        if head == None or head.next == None: return True
        slow,fast = head,head#慢指针、快指针
        #找到中间节点
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
        #找到中间节点后让fast指针指向slow->next;
        fast = slow.next
        slow.next = None
        newList = None
        #进行后半部分的翻转
        while fast != None:
            newList = fast.next
            fast.next = slow
            slow = fast
            fast = newList
        #判断回文
        newList = slow
        fast = head
        while fast != None and newList != None:
            if fast.val != newList.val:return False
            fast = fast.next
            newList = newList.next
        return True

JavaScript版本:

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
function isPail( head ) {
    // write code here
    if(head == null || head.next == null) return true;
        let slow = head;//慢指针
        let fast = head;//快指针
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //找到中间节点后让fast指针指向slow->next;
        fast = slow.next;
        slow.next = null;
        let newList = null;
        while(fast != null){
            newList = fast.next;
            fast.next = slow;
            slow = fast;
            fast = newList;
        }
        newList = slow;
        fast = head;
        //判断回文
        while (fast != null && newList != null) { 
            if (fast.val != newList.val) {
                return false;
            }
            fast = fast.next; 
            newList = newList.next; 
        }
        return true;
}
module.exports = {
    isPail : isPail
};