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

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

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

- 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
};
全部评论
超时了,python
点赞 回复 分享
发布于 2021-04-07 23:06

相关推荐

06-10 21:15
门头沟学院 Java
宁阿:好多这种没🧠的公司,他们估计都不知道毕业的人不能给安排实习岗
实习吐槽大会
点赞 评论 收藏
分享
05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
投递美团等公司9个岗位
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
18
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务