学会-nowcoder-两道单链表题(详解)

前言

这两道题都有共同的地方，就是一个节点被两个节点指向，所以做的时候要注意。

一、链表回文结构题链接

题目描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)，的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例1：

测试样例2：

题目思路

1. 想知道是否是回文结构，我们第一步就是要先找到中间的节点。利用快慢指针
2. 从中间的节点开始，把我们的都逆置一下。
3. 之后就开始把第一个节点和中间的节点比较。

注意：在这里我们要注意一个细节，在逆置的时候，
中间节点的前一个节点还是指向中间节点的，我们上图描述。

class PalindromeList {
    
public:bool chkPalindrome(ListNode* A) {
    // write code here//找中间节点if(A==NULL||A->next==NULL){
    return true;}struct ListNode*slow=A;struct ListNode*fast=A;while(fast!=NULL&&fast->next!=NULL){
    slow=slow->next;fast=fast->next->next;}//逆置struct ListNode*mid=slow;struct ListNode*midTail=NULL;struct ListNode*trace=NULL;while(mid){
    midTail=mid->next;mid->next=trace;trace=mid;mid=midTail;}//比较while(trace&&A){
    if(A->val!=trace->val){
    return false;}A=A->next;trace=trace->next;}return true;}
};

二、链表分割链接链接

题目描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

测试样例1：

测试样例2：

题目思路

1. 我们先把链表分割成一个小于x的链表和一个大于x的链表
2. 在把两条链表链接
   注意：在这里我们要注意一个细节
   当最后一个链表的节点小于x的时候会形成一个环型链表。
   所以最后要置空那个指向。
   上图：
   

class Partition {
    
public:ListNode* partition(ListNode* pHead, int x) {
    // write code herestruct ListNode*cur=pHead;struct ListNode*greatTail=NULL;struct ListNode*lessList=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*greatList=greatTail=(struct ListNode*)malloc(sizeof(struct ListNode));lessList->next=NULL;greatList->next=NULL;struct ListNode*curTail=NULL;struct ListNode*head=NULL;head=lessList;while(cur){
    curTail=cur->next;if(cur->val<x){
    lessList->next=cur;lessList=cur;cur=curTail;}else{
    greatTail->next=cur;greatTail=cur;cur=curTail;}}//链接两个链表//置空greatTail->next=NULL;lessList->next=greatList->next;return head->next;}
};

总结

希望看完这篇文章的你，有收获。