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

力扣重排链表-143

news 2025/7/15 9:19:57

重排链表-143

/*** 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) {//利用快慢指针找到链表的中点//慢指针走一步，快指针走两步，快指针走到头循环结束后，慢指针的位置就是链表的中点ListNode* slow = head;ListNode* fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}//反转链表ListNode* cur = NULL;ListNode* pre = slow->next;slow->next = NULL;//反转链表之前要切断前半部分while (pre != NULL){ListNode* t = pre->next;pre->next = cur;cur = pre;pre = t;}//合并链表，将后半部分反转之后的链表中的每个节点插入到前半部分链表每个节点的中间位置ListNode* h = head;ListNode* c = cur;while (c != NULL) {/*将前半链表和后半部分链表的当前节点的下一个节点保存下来，以便后续的连接操作，因为后面会改变指向，会找不到下一个节点*/ListNode* temph = h->next;ListNode* tempc = c->next;/*将前半部分链表的h节点的下一个节点指向c，将后半部分链表的c节点的下一个节点指向temph，就是前半部分链表的h节点的下一个节点（没指向c节点之前的下一个节点）*/h->next = c;c -> next = temph;/*改变指向过后，更新h和c为原来节点（前半部分链表和后半部分链表都没改变指向之前）的下一个节点*/h = temph;c = tempc;//继续进行循环拼接，直到c为NULL结束循环，则拼接完成}   }
};

每日问题

什么是多态性？C++中如何实现多态？多态性的好处是什么？

什么是多态性？

多态性（Polymorphism）是面向对象编程中的一个重要概念，指的是同一个操作或方法可以作用于不同类型的对象，并表现出不同的行为。它使得一个接口可以根据对象的实际类型进行不同的操作。

多态的两种类型：

1.编译时多态（静态多态，早绑定）：

在编译时决定调用哪个函数。

主要通过函数重载（Function Overloading）和运算符重载（Operator Overloading）实现。

2.运行时多态（动态多态，晚绑定）：

在运行时根据对象的实际类型来决定调用哪个函数。

主要通过虚函数（Virtual Functions）和继承关系来实现。

C++中如何实现多态？

1. 编译时多态（静态多态）

函数重载（Function Overloading）：允许多个同名函数根据参数个数或类型不同而有不同的实现。

#include <iostream>
using namespace std;class Printer {
public:void print(int i) {cout << "Printing int: " << i << endl;}void print(double d) {cout << "Printing double: " << d << endl;}
};int main() {Printer p;p.print(10);    // 调用 print(int)p.print(3.14);  // 调用 print(double)return 0;
}

运算符重载（Operator Overloading）：允许自定义运算符的行为。

#include <iostream>
using namespace std;class Complex {
public:int real, imag;Complex(int r, int i) : real(r), imag(i) {}// 重载加法运算符Complex operator + (const Complex &other) {return Complex(real + other.real, imag + other.imag);}void display() {cout << real << " + " << imag << "i" << endl;}
};int main() {Complex c1(2, 3), c2(4, 5);Complex c3 = c1 + c2;  // 调用重载的 + 运算符c3.display();           // 输出: 6 + 8ireturn 0;
}

2. 运行时多态（动态多态）

虚函数（Virtual Function）和继承： C++ 的多态性主要通过基类指针或引用指向派生类对象并通过虚函数实现。虚函数允许子类重写父类的函数，并在运行时根据对象的实际类型调用相应的函数。

#include <iostream>
using namespace std;// 基类
class Animal {
public:virtual void sound() {  // 虚函数cout << "Animal makes a sound" << endl;}
};// 派生类
class Dog : public Animal {
public:void sound() override {  // 重写虚函数cout << "Dog barks" << endl;}
};class Cat : public Animal {
public:void sound() override {  // 重写虚函数cout << "Cat meows" << endl;}
};int main() {Animal* animal1 = new Dog();  // 基类指针指向派生类对象Animal* animal2 = new Cat();  // 基类指针指向另一个派生类对象animal1->sound();  // 调用 Dog 类的 sound() 函数animal2->sound();  // 调用 Cat 类的 sound() 函数delete animal1;delete animal2;return 0;
}

输出：