首页 > 其他分享 >代码随想录之链表刷题总结

代码随想录之链表刷题总结

时间:2024-10-31 19:20:35浏览次数:3  
标签:ListNode cur val 随想录 next 链表 节点 刷题

目录

1.链表理论基础

2.移除链表元素

3.设计链表

4.翻转链表

5.两两交换链表中的节点

6.删除链表中的第N个节点

7.链表相交

8.环形链表


1.链表理论基础

链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。

链表的入口节点称为链表的头结点也就是head。

如下图所示:

链表的类型

单链表

也就是刚才所说的

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

如图所示:

循环链表

循环链表,顾名思义,就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

链表的存储方式

数组是在内存中是连续分布的,但是**链表在内存中不是连续分布**的。

链表是**通过指针域的指针链接在内存中各个节点**

所以链表中的节点在内存中不是连续分布的 ,而是**散乱分布在内存中的某地址上**,分配机制取决于操作系统的内存管理。

如图所示:

这个链表起始节点为2, 终止节点为7,  各个节点分布在内存的不同地址空间上,通过指针串联在一起。

链表的定义

C/C++的定义链表节点方式,如下所示:

struct ListNode {
	int val;//存储节点上面的元素值
	ListNode* next;//用于指向链表的下一个节点,初始时被设置wULL,表示当前节点是链表的末尾
	ListNode(int x) : val(x),next(NULL) {}//构造函数,初始化ListNode的实例,接收一个整型参数x,并将这个值赋给当前节点的val成员,
	//同时将next指针初始化为NULL,表示这个节点后面没有更多的节点

};
/*操作示例*/
ListNode* head = new ListNode(1);//创建链表的头节点,值为1
head->next = new ListNode(2);//在头节点后面添加一个新的节点,值为2

有同学说了,我不定义构造函数行不行,答案是可以的,C++默认生成一个构造函数。

但是这个构造函数不会初始化任何成员变量,下面我来举两个例子:

通过自己定义构造函数初始化节点:

ListNode* head = new ListNode(5);

使用默认构造函数初始化节点:

ListNode* head = new ListNode();
head->val = 5;

所以如果不定义构造函数使用默认构造函数的话,在初始化的时候就不能直接给变量赋值!

链表的操作

删除节点

删除D节点,如图所示:

只要将C节点的next指针 指向E节点就可以了。

那有同学说了,D节点不是依然存留在内存里么?只不过是没有在这个链表里而已。

是这样的,所以在C++里最好是再手动释放这个D节点,释放这块内存。

其他语言例如Java、Python,就有自己的内存回收机制,就不用自己手动释放了。

添加节点

如图所示:

可以看出链表的增添和删除都是O(1)操作,也不会影响到其他节点。

但是要注意,要是删除第五个节点,需要从头节点查找到第四个节点通过next指针进行删除操作,查找的时间复杂度是O(n)。

性能分析

把链表的特性和数组的特性进行一个对比,如图所示:

数组在定义的时候,长度就是固定的,如果想改动数组的长度,就需要重新定义一个新的数组。

链表的长度可以是不固定的,并且可以动态增删, 适合数据量不固定,频繁增删,较少查询的场景。

2.移除链表元素

题目:

题意:删除链表中等于给定值 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 输出:[]

思路:

先设置虚拟头节点,因为第一个节点也有可能是val值,然后移除的操作其实就是val值的前一个节点直接跳过val节点,指向val的下一个节点

注意:跳过的节点记得手动释放一下内存,节省空间

代码如下:

class Solution {
public:
	ListNode* removeElement(ListNode* head, int val) {
		ListNode* dummyHead = new ListNode(0);
		dummyHead->next = head;
		ListNode* cur = dummyHead;
		while (cur->val != NULL) {
			if (cur->next->val == val) {
				ListNode* tmp = cur->next;
				cur->next = cur->next->next;
				delete tmp;
			}
			else {
				cur = cur->next;
			}
		}
		head = dummyHead->next;
		delete dummyHead;
		return head;
		
	}
};

3.设计链表

题目

a.get(index):获取链表中第 index 个节点的值。如果索引无效,则返回 - 1。
b.addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
c.addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
d.addAtIndex(index, val):在链表中的第 index 个节点之前添加值为 val  的节点。
如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
e.deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

注意:

注意初始定义链表的状态

自己在纸上面写一遍

注意index的区间边界,搞清楚链表中的移动大小,以便在正确的位置做插入删除操作

代码如下:

class MyLinkedList {
public:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int val) :val(val), next(nullptr) {}
    };

    // 初始化链表
    MyLinkedList() {
        _dummyHead = new ListNode(0); // 这里定义的头结点 是一个虚拟头结点,而不是真正的链表头结点
        _size = 0;
    }
    //a.get(index):获取链表中第 index 个节点的值。如果索引无效,则返回 - 1。
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        else {
            ListNode* cur = _dummyHead->next;
            while (index--) {
                cur = cur->next;
            }
            return cur->next->val;
        }
    }
    //b.addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
    void addAtHead(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    //c.addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
    void addAtTail(int val) {
        ListNode* newNode = new ListNode(val);
        ListNode* cur = _dummyHead;
        while (cur->next != NULL) {
            cur = cur->next;
        }
        newNode->next = cur;

    }
//d.addAtIndex(index, val):在链表中的第 index 个节点之前添加值为 val  的节点。
//如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
    void addAtIndex(int index, int val) {
        if (index > _size) return;
        if (index < 0) index = 0;
        ListNode* newNode = new ListNode(val);
        ListNode* cur = _dummyHead;
        while (index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    //e.deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
    void deleteAtIndex(int index) {
        ListNode* cur = _dummyHead;
        if (index > _size - 1 || index < 0) {
            return;
        }
        while (index--) {
            cur = cur->next;
        }
        ListNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        temp = NULL;
        _size--;

    }
    //打印链表
    void printLinkedList() {
        ListNode* cur = _dummyHead;
        while (cur->next != NULL) {
            cout << "cur->next-val = " << cur->next->val << endl;
            cur = cur->next;
        }
        cout << endl;
    }
public:
    ListNode* _dummyHead;
    int _size;
};

4.翻转链表

题目:

题意:反转一个单链表(是将箭头翻转,不是里面的元素进行翻转)

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路:

设置双指针法,一个pre先指向NULL,然后cur在head节点,不断更新指向

注意:

使用temp先保存cur->next,因为指向改变了,不存储的话无法继续进行

代码如下:

class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		ListNode* pre = NULL;
		ListNode* cur = head;
		ListNode* temp = new ListNode(0);
		while (cur) {
			temp = cur->next;
			cur->next = pre;
			//更新pre和cur
			pre = cur;
			cur = temp;
		}
		return pre;

	}
};

5.两两交换链表中的节点

题目:

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

思路:

按照下图中的三部进行操作即可

注意:

记得保存cur->next与cur->next->next->next的值,因为指向发生了改变

代码:

class Solution {
public:
	ListNode* swapPairs(ListNode* head) {
		ListNode* dummyhead = new ListNode(0);
		dummyhead->next = head;
		ListNode* cur = dummyhead;
		while (cur->next != nullptr && cur->next->next != nullptr) {
			ListNode* temp = cur->next;
			ListNode* temp1 = cur->next->next->next;
			/*dummyhead->next = temp1;
			temp1->next = temp;
			temp = cur->next->next->next;*///错误写法,不可取
			cur->next = cur->next->next;
			cur->next->next = temp;
			cur->next->next->next = temp1;

			cur = cur->next->next;
		}
		ListNode* result = dummyhead->next;
		delete dummyhead;
		return result;
	}
};

6.删除链表中的第N个节点

题目:

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]

示例 2:

输入:head = [1], n = 1 输出:[]

示例 3:

输入:head = [1,2], n = 1 输出:[1]

思路:

使用双指针法进行解决,先定义fast指针和slow指针,初始化为虚拟头节点,fast先走n步,然后俩指针一起开始移动,直到fast变为NULL停止,此时slow指向的正好是删除节点的前一个节点,这是再改变节点指向即可

注意:

slow一定要在删除节点的前一个,不然无法继续操作

对于while循环中的逻辑要充足考虑,不要漏掉情况

代码如下:

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		ListNode* dummyhead = new ListNode(0);
		dummyhead->next = head;
		ListNode* slow = dummyhead;
		ListNode* fast = dummyhead;
		while (n--&&fast->next!=nullptr) {
			fast = fast->next;
		}
		while (fast->next != nullptr) {
			slow = slow->next;
			fast = fast->next;
		}
		slow->next = slow->next->next;
		return dummyhead->next;
	}
};

7.链表相交

题目:

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

图示两个链表在节点 c1 开始相交:

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 **保持其原始结构**

思路:

此时一定要充分理解链表相交,:若两个链表相交,则两个链表有共同的节点,从这个节点之后,后面的节点都会重叠,直到链表结束,若相交,则两个链表呈现Y字型

 先计算两个列表的长度差值,让curA和curB这两个指针对齐,然后再移动,判断指针是否相等

如下图:

注意:

明确链表相交是什么

判断的是指针,不是数值

代码:

class Solution {
	ListNode* listjiao(ListNode* headA, ListNode* headB) {
		ListNode* curA = headA;
		ListNode* curB = headB;
		int sizeA = 0;
		int sizeB = 0;

		while (curA != nullptr) {
			sizeA += 1;
			curA = curA->next;
		}

		while (curB != nullptr) {
			sizeB += 1;
			curB = curB->next;
		}

		if (sizeB > sizeA) {
			swap(sizeA, sizeB);
			swap(headA, headB);
		}

		int gap = sizeA - sizeB;
		while (gap--) {
			curA = curA->next;
		}

		while (curA != nullptr) {
			if (curA == curB) {
				return curA;
			}
			else {
				curA = curA->next;
				curB = curB->next;
			}
		}
		return NULL;
	}
};

8.环形链表

题目:

题意: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

思路:

判断1:链表是否有环
快慢指针法,从头节点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,若相遇就是有环。
判断2:环的入口节点
分别从头节点以及相遇节点出发一个指针,每次只走一个,相遇的时候就是入口节点

注意:

最后返回的是环形入口节点

代码:

class Solution {
public:
	ListNode* detecCycle(ListNode* head) {
		ListNode* fast = head;
		ListNode* slow = head;
		//while (fast->next->next != nullptr && slow != nullptr) {//啰嗦了,可以改一下
		while(fast!=NULL&&fast->next!=NULL) {
			fast = fast->next->next;
			slow = slow->next;
			//快慢指针相遇
			if (fast == slow) {
				ListNode* index1 = head;
				ListNode* index2 = fast;
				while (index1 != index2) {
					index1 = index1->next;
					index2 = index2->next;
				}
				return index1;
			}
		}
		return nullptr;
	}
};

标签:ListNode,cur,val,随想录,next,链表,节点,刷题
From: https://blog.csdn.net/Lllongroad/article/details/143405126

相关文章

  • 《链表篇》---两两交换链表中的节点(中等)
    题目传送门1.定义一个虚拟节点链接链表2.定义一个当前节点指向虚拟节点3.在当前节点的下一个节点和下下一个节点都不为null的情况下。定义node1和node2。保存当前节点后面两个节点的地址。cur.next=node2;node1.next=node2.next;node2.next=node1;cur=node1;4.......
  • 《链表篇》---删除链表的倒数第N个节点(中等)
    题目传送门 方法一:计算链表长度(迭代)1.计算链表长度,并且定义哑节点链接链表。2.从哑节点开始前进length-n次。即为被删除节点的前置节点。3.进行删除操作。4.返回哑节点的后置节点classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){......
  • 牛客网刷题(4)(Java之(static)静态变量、静态方法、静态代码块、静态内部类)
    目录一、static关键字。(1)牛客网题目。(2)总结。<1>静态变量。(类变量)1、特点。2、补充与注意。3、代码演示。<2>静态方法1、特点。2、补充与注意。3、代码演示。<3>静态代码块。1、特点。2、补充与注意。3、代码演示。<4>静态内部类。1、特点。2、注意事项。3......
  • 代码随想录刷题学习日记
    仅为个人记录复盘学习历程,解题思路来自代码随想录代码随想录刷题笔记总结网址:代码随想录257.二叉树的所有路径给定一个二叉树,返回所有从根节点到叶子节点的路径。提供参数:根结点root关键思路:由于需要返回从根节点到叶子节点的路径,故采用前序遍历,每次遍历时将当前节点加......
  • Leetcode刷题Python之3165.不包含相邻元素的子序列的最大和
    提示:利用线段树解决不包含相邻元素的子序列最大和问题。文章目录一、题目描述示例二、解题思路1.思路分析2.线段树的状态设计3.线段树的操作三、代码实现代码详细解释四、总结时间复杂度分析一、题目描述给定一个整数数组nums和一个二维数组queries,其中q......
  • 刷题总结——区间和
    前缀和前缀和是一种解决区间求和问题的辅助方法,前缀和只适用于固定区间(数组、树等),如果区间元素发生变化,则不适用,此时需要考虑树状数组、线段树等方式。问题类型常见的问题也是和DP一样,求最大/最小/方案数。类型题目备注前缀和+哈希LC560两数之和思路前缀和+......
  • 代码随想录算法训练营day31| 56. 合并区间 738.单调递增的数字
    学习资料:https://programmercarl.com/0056.合并区间.html#算法公开课贪心PART5over学习记录:56.合并区间(也是找重叠区间,但是是跟result[-1]比,只用比右边界;更新result[-1][1]为更大值)点击查看代码classSolution(object):defmerge(self,intervals):"""......
  • 代码随想录算法训练营第十二天| 226.翻转二叉树、101. 对称二叉树、104.二叉树的最大
    226.翻转二叉树题目链接:.-力扣(LeetCode)文章讲解:代码随想录视频讲解:听说一位巨佬面Google被拒了,因为没写出翻转二叉树|LeetCode:226.翻转二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦!快来打卡!本期视频的文字讲解版在「代码随想录」刷题网站:programmercarl.com......
  • 代码随想录算法训练营第十三天| 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子
    110.平衡二叉树题目链接:.-力扣(LeetCode)文章链接:代码随想录视频链接:后序遍历求高度,高度判断是否平衡|LeetCode:110.平衡二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦!快来打卡!本期视频的文字讲解版在「代码随想录」刷题网站:programmercarl.com,这里刷题顺序,详......
  • 代码随想录 -- 动态规划 -- 01背包理论基础
    46.携带研究材料(第六期模拟笔试)思路:dp[i][j]含义:在(0,i)之间任意选取物品放入容量为j的背包中,使背包的价值最大。递推公式:当前背包容纳不下第i个物品,不选第i个物品,此时背包的价值:dp[i][j]=dp[i-1][j]。当前背包容纳得下第i个物品时,且选择第i个物品,此时背包的价值:dp[i][j......