Leetcoder Day3｜链表理论基础｜203.移除链表元素｜707.设计链表｜206.反转链表

2023-12-31 04:34:01

语言：Java/C++?

链表理论基础

单链表

链表理论基础

链表是一种通过指针串联在一起的线性结构

链表中的节点在内存中不是连续分布的
每个节点由两部分组成，数据域+指针域，最后一个节点的指针域指向null
通过指针域的指针链接内存中各个节点。

如图为链表的存储方式，?各个节点分布在内存的不同地址空间上，通过指针串联在一起

单链表

符合链表的一般特性，单链表中的指针域只能指向节点的下一个节点。

双链表

每个节点有两个指针域，一个指向下一个节点，一个指向上一个节点；
既可以向前查询也可以向后查询。

循环链表

链表首尾相连，可以用来解决约瑟夫环问题

🔔约瑟夫问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

链表的定义

C++

struct ListNode{
        int val; // 节点上存储的元素
        ListNode *next;  // 指向下一个节点的指针
        ListNode(int x): val(x), next(Null){}// 节点的构造函数
}



//创建链表
void CreatList(ListNode* linklist, int n)
{
	//链表动态增加元素
	//定义创建新的元素的辅助指针*p
	ListNode* p = linklist;
	for (int i = 0; i < n; i++)
	{
		ListNode* newNode = new ListNode(i);	//开辟了链表的存储空间，不能用delete释放
		newNode->next = nullptr;			
		p->next = newNode;						//辅助指针把新创建的节点接到链表的尾巴
		p = newNode;
	}

Java

public class ListNode{

    int val;
    ListNode next;
    // 节点的构造函数(无参)
    public ListNode(){
    }
    // 节点的构造函数(有一个参)
    public ListNode(int val){
        this.val=val;
    }
    // 节点的构造函数(有2个参)
    public ListNode(int val,  ListNode next){
        this.val=val;
        this.next=next
    }
    
}

Python

Class ListNode{
    def __init__(self, val, next=None):
        self.val=val;
        self.next=next;
}

链表的操作

删除节点

删除时，只需要将CD之间的链去掉，即将C节点的next指针指向E节点即可。

可以使用原链表来直接进行删除操作，也可以设置一个虚拟头结点再进行删除操作

这时D节点依然存留在内存里，C++最好是再手动释放这个D节点，释放这块内存。如果使用java ，python的话就不用手动管理内存;
删除第n个节点，需要从头节点查找到第n-1个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

c++：

void deleteNode(ListNode* linklist, int index)
{
	int getval = GetIndexValue(linklist, index+1);
	if (index <= LengthList(linklist))
	{
		ListNode* p = linklist;
		for (int i = 0; i < index; i++)
		{
			p = p->next;
		}
		ListNode* tmp = new ListNode(0);
		tmp = p->next;
		p->next = tmp->next;
		delete tmp;
		cout << "删除元素" << getval  << "成功！" << endl;
	}
}

添加节点

添加节点就是先把指向原先下一个节点的链断掉，将原节点的next指针指向新的节点，将新的节点的next指针指向原本的下一个节点。

//在链表index位置插入val
void insertNode(ListNode* linklist, int index, int val)
{
	//判断是否越界
	if (index <= LengthList(linklist))
	{
		ListNode* p = linklist;
		for (int i = 0; i < index ; i++)
		{
			p = p->next;
		}
		ListNode* tmp = new ListNode(val);
		tmp->next = p->next;
		p->next = tmp;
		cout << "插入元素成功！" << endl;
	}
}

链表的增添和删除都是O(1)操作

数组🆚链表

数组长度是固定的，若想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以不固定，可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。

203.移除链表元素?

给你一个链表的头节点?head?和一个整数?val?，请你删除链表中所有满足?Node.val == val?的节点，并返回新的头节点?

示例 1：输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2：输入：head = [], val = 1 输出：[]

示例 3：输入：head = [7,7,7,7], val = 7 输出：[]

🏁解题思路：

一般涉及到移除链表元素时，会遇到一个特殊的情况：移除的是头节点。移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。因此如果在原链表上进行操作，需要将头结点向后移动一位就可以，需要单独写一段逻辑来处理移除头结点：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

也可以以一种统一的逻辑来移除链表的节点，就是设置一个虚拟头结点在进行删除操作，如图添加一个虚拟头结点为新的头结点后，移除头节点的操作就和移除其他节点操作一样了。??最后返回头结点的时候，要return dummyNode->next;，这才是新的头结

C++：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head==NULL){
            return head;
        }
        ListNode* dummyHead= new ListNode(0);
        dummyHead->next=head;
        ListNode* cur=dummyHead; // 设置指针
        while(cur->next!=NULL){
            if(cur->next->val==val){
                ListNode* temp=cur->next;
                cur->next=cur->next->next;
                delete temp;
            }
            else{
                cur=cur->next;
        }
    }
    head=dummyHead->next;
    delete dummyHead;
    return head;
    }
};

Java：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return head;
        }
        ListNode dummyHead=new ListNode(-1, head);
        dummyHead.next=head;
        ListNode cur=dummyHead;
        while(cur.next!=null){
            if(cur.next.val==val){
                ListNode temp=cur.next;
                cur.next=cur.next.next;
            }
            else{
                cur=cur.next;
            }
        }
        return dummyHead.next;
    }
}

707.设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val?和?next?。val?是当前节点的值，next?是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性?prev?以指示链表中的上一个节点。假设链表中的所有节点下标从?0?开始。

实现?MyLinkedList?类：

MyLinkedList()?初始化?MyLinkedList?对象。
int get(int index)?获取链表中下标为?index?的节点的值。如果下标无效，则返回?-1?。
void addAtHead(int val)?将一个值为?val?的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val)?将一个值为?val?的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val)?将一个值为?val?的节点插入到链表中下标为?index?的节点之前。如果?index?等于链表的长度，那么该节点会被追加到链表的末尾。如果?index?比长度更大，该节点将?不会插入?到链表中。
void deleteAtIndex(int index)?如果下标有效，则删除链表中下标为?index?的节点。

🏁解题思路：

这是一个更加综合的题，从基础理论和上一个移除链表元素中我们学习了链表的基本操作和构建虚拟头节点。本题实际是设计链表的五个接口：

获取链表第index个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第index个节点前面插入一个节点
删除链表的第index个节点：这里注意加上一句tmp=nullptr，否则tmp会成为乱指的野指针。

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化链表
    MyLinkedList() {
        dummyHead = new LinkedNode(0); // 定义一个虚拟头节点
        size = 0;
    }

    int get(int index) {
        if (index > (size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = dummyHead->next;
        while(index--){ // 如果--index 就会陷入死循环
            cur = cur->next;
        }
        return cur->val;
    }

    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
    }

    // 在链表最后面添加一个节点
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        size++;
    }


    void addAtIndex(int index, int val) {

        if(index > size|index < 0) return;      
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }

    // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
    void deleteAtIndex(int index) {
        if (index >= size || index < 0) {
            return;
        }
        LinkedNode* cur = dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        temp=nullptr;
        size--;
    }

    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int size;
    LinkedNode* dummyHead;

};

206.反转链表?

给你单链表的头节点?head?，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

🏁解题思路：

双指针法

这道题如果用暴力方法解决，其实新定义一个列表，用for循环存储就可以，但是这样对较浪费内存，因此，可以采取改变列表next指针方向的思路，进行原地反转。

定义两个指针，pre和cur，一个指向当前节点，一个指向当前节点的前一个节点，如果是头节点就没有前一个节点，所以我们可以继续采用构造虚拟头节点的思路。这里还要初始化一个temp节点用来保存当前节点的下一个节点，因为当前的下一个节点，即将成为反转后的前节点，指针断掉并转向以后会有获取不到下一个节点的位置，因此设置一个temp节点。此外，还要注意，先移动pre，再移动cur，因为这样才能让pre走到真正的cur。因此循环的过程是这样的，先让pre指向前一个节点，再让cur指针指向头节点，然后，让temp存储cur的下一个节点，然后不断按照先移动pre后移动cur的顺序，不断循环直到cur指向空节点，链表也反转完毕了。?

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

时间复杂度: O(n)
空间复杂度: O(1)

递归法

首先要明确递归的概念：指在函数的定义中使用函数自身的方法。其逻辑本质上和双指针法是一样的。下面来梳理代码的具体思路。

首先因为主函数是reverseList()，因此需要新定义一个reverse函数实现真正的翻转功能。按照双指针的思路，reverse函数的传入参数直接定义为pre和cur这两个节点。对于它们的初始化值，pre=NULL和cur=head，因此，在调用reverse时参数为reverse(NULL, head)。

在reverse中确定循环终止的条件，即cur指向空节点时，此时翻转后的头节点应该是pre。此时还是要设置temp保存下一个cur的位置，然后改变方向，让cur->next = pre。接下来移动pre与cur指针，即进入下一个循环，因此调用reverse本身，pre移动到当前cur的位置，cur移动到提前保存的下一个节点temp的位置，因此reverse内部参数为reverse(cur, temp)。至此，递归方法完成。

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};

时间复杂度: O(n), 要递归处理链表的每个节点
空间复杂度: O(n), 递归调用了 n 层栈空间

上面的递归写法和双指针法实质上都是从前往后翻转指针指向，也可以采用从后往前翻转指针指向的思路：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边缘条件判断
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;
        
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode *last = reverseList(head->next);
        // 翻转头节点与第二个节点的指向
        head->next->next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head->next = NULL;
        return last;
    }
};

今日心得

今天几道题的思路都是不难的，就是再一次看出来对于语法使用的生疏，尤其是链表的构造，需要多多练习。

文章来源:https://blog.csdn.net/weixin_36675391/article/details/135291324
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！

Leetcoder Day3｜链表理论基础｜203.移除链表元素 ｜707.设计链表 ｜206.反转链表

链表理论基础

单链表

循环链表

链表的定义

链表的操作

删除节点

添加节点

数组🆚链表

203.移除链表元素?

🏁解题思路：

707.设计链表

🏁解题思路：

206.反转链表?

🏁解题思路：

双指针法

递归法

今日心得

Leetcoder Day3｜链表理论基础｜203.移除链表元素｜707.设计链表｜206.反转链表