当前位置：首页 > article >正文

每日计划-1207

article 2025/2/1 2:01:13

1. 完成 143. 重排链表

题目要不能只改变值，所以不能用stack（栈）实现单纯值操作。

法一：利用线性表vector，vector<ListNode*>vec;这句代码实现储存操作，采用中断处理，代码：if(i==j){
break;)实现。

法二：经典操作：找链表中点，反转链表，合并链表。

法一代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==nullptr)return ;
        vector<ListNode*>vec;//使用节点线性表
        ListNode*p=head;
        //储存节点
        while(p){
            vec.emplace_back(p);
            p=p->next;
        }
        
        int i=0,j=vec.size()-1;//数组大小下表减1 才是数组最后下标
        while(i<j){//交替重置链表
            vec[i]->next=vec[j];
            i++;
           //实现交替操作
            if(i==j){
                break;
            }
            vec[j]->next=vec[i];
            j--;
        }
        vec[i]->next=nullptr;
    }
};

法二代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:


    
    void reorderList(ListNode* head) {
        if(head==nullptr){
            return;
        }
        ListNode*mid=middlNode(head);
        ListNode*l1=head;
        ListNode*l2=mid->next;
        mid->next=nullptr;//重置节点
        l2=reverseList(l2);
        mergeList(l1,l2);
    }



    //找链表中点
    ListNode*middlNode(ListNode*head){
        ListNode*slow=head;
        ListNode*fast=head;
        //经典快慢指针操作 你走一步 我走两步 我们始终是两倍差距
        while(fast->next!=nullptr&&fast->next->next!=nullptr){//奇偶差别
            slow=slow->next;
            fast=fast->next->next;
      
        }
        return slow;
    }

    //反转链表
    ListNode*reverseList(ListNode*head){
        ListNode*prev=nullptr;
        ListNode*curr=head;
        //经典三变量问题 终止条件为 curr->next==nullptr 
        //不断实现将头节点放在链表最后
        while(curr!=nullptr){
            ListNode*nextTemp=curr->next;
            curr->next=prev;
            prev=curr;
            curr=nextTemp;
        }
        return prev;
    }
   
   /*经典递归反转
   ListNode*reverseList(ListNode*head){
        if(head->next==nullptr||head->next->next==nullptr){
            return head;
        }
        ListNode*newNode=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
    }*/

//交替插入链表
    void mergeList(ListNode* l1, ListNode* l2) {
            ListNode* l1_tmp;
            ListNode* l2_tmp;
            while (l1 != nullptr && l2 != nullptr) {
                l1_tmp = l1->next;
                l2_tmp = l2->next;

                l1->next = l2;
                l1 = l1_tmp;

                l2->next = l1;
                l2 = l2_tmp;
            }
        }

    

};