【OJ】牛客链表刷题

zxctscl

发布于 2024-01-23 09:00:28

1030

发布于 2024-01-23 09:00:28

文章被收录于专栏：zxctscl个人专栏

这里两道与链表有关的题目均来自牛客。

1. 链表分割

1.1 题目分析

因为这里代码不能选择用c语言写，所以选择用c++,因为c++兼容c。题目要求分割链表，我们可以直接弄成两个带哨兵位的链表，这样插入时就不用判断链表里面有没有节点。

    head1=tail1=(ListNode*)malloc(sizeof(ListNode));
    head2=tail2=(ListNode*)malloc(sizeof(ListNode));

一个链表放小于x的节点，直接用尾插就能实现，

          if(cur->val<x)
           {
            tail1->next=cur;
            tail1=tail1->next;
           }

另一个链表放大于等于x的节点，也使用尾插入。

 else {
            tail2->next=cur;
            tail2=tail2->next;
           }

最后把两个链表连接就行，

tail1->next=head2->next;

连接之后不要忘记把链表2的尾节点置空tail2->next=NULL，返回没有哨兵位的头节点pHead=head1->next，而头节点是我们自己在做的时候申请的，不要忘记free。

free(head1);
free(head2);

1.2 代码

class Partition {
  public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* cur=pHead;
        ListNode* head1, *tail1,*head2,*tail2;
        head1=tail1=(ListNode*)malloc(sizeof(ListNode));
        head2=tail2=(ListNode*)malloc(sizeof(ListNode));
        while(cur)
        {
           if(cur->val<x)
           {
            tail1->next=cur;
            tail1=tail1->next;
           }
           else {
            tail2->next=cur;
            tail2=tail2->next;
           }
           cur=cur->next;
        }
        tail1->next=head2->next;
        tail2->next=NULL;
        pHead=head1->next;
        free(head1);
        free(head2);

        return pHead;
    }
};

2. 链表的回文结构

这里同样是不能选择用c语言写，所以选择用c++,因为c++兼容c。

2.1 题目分析

我们先搞清楚什么是回文结构，回文结构简单来说就是对称，看题目给的例子1 2 2 1，是不是就是第一个与最后一个是相等的，第二个与倒数第二个是相同的，题目这个给的是数为偶数的情况。为奇数也是一样的像1 2 3 2 1，也是一样的道理。那么我们是不是就可以想到把原链表拆为两部分，把后边部分逆置一下，再与前半部分比较就行了。这里得计算哪里开始是后半段，这里就得用到快慢指针，不管是奇数个还是偶数个，把中间位置的节点放在新链表中，最后与拆后的链表比较完，就算新链表还剩下一个，拆后的已经比较完了，就说明还是回文结构。慢指针slow走一步，快指针走两步，当快指针fast走完或者快指针fast的next为空就结束，返回慢指针指向的位置。这里得重新写一个函数，返回慢指针。

       struct ListNode* MidNode(ListNode* A) {
        ListNode* slow = A, *fast = A;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;

    }

然后在新链表开始进行头插，返回新链表的头节点，也直接写一个

struct ListNode* NewList(struct ListNode* A) {

        ListNode* cur = A;
        ListNode* newhead;
        while (cur) {
            ListNode*next=cur->next;
        cur->next=newhead;
        newhead=cur;
        cur=next;

        }
        return newhead;
    }

再将新链表与拆了的链表进行比较。

       bool chkPalindrome(ListNode* A) {
       struct ListNode* mid=MidNode(A);
       struct ListNode* newhead=NewList(mid);
        while(A&&newhead)
        {
           if(A->val!=newhead->val)
               return false;
        
           A=A->next;
           newhead=newhead->next;

        }
        return true;

2.2 代码

class PalindromeList {
  public:
    struct ListNode* NewList(struct ListNode* A) {

        ListNode* cur = A;
        ListNode* newhead;
        while (cur) {
            ListNode*next=cur->next;
        cur->next=newhead;
        newhead=cur;
        cur=next;

        }
        return newhead;
    }
    struct ListNode* MidNode(ListNode* A) {
        ListNode* slow = A, *fast = A;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;

    }

    bool chkPalindrome(ListNode* A) {
       struct ListNode* mid=MidNode(A);
        struct ListNode* newhead=NewList(mid);
        while(A&&newhead)
        {
           if(A->val!=newhead->val)
               return false;
        
           A=A->next;
           newhead=newhead->next;

        }
        return true;
        // write code here
    }
};