反转链表
给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
如当输入链表{1,2,3}时,经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。以上转换过程如下图所示:
示例:
输入:{1,2,3}
返回值:{3,2,1}
好久好久没有刷题了,这一年大多在写Shell脚本或者Python脚本去了,已经忘记自己是C++起家的了,好几天前大页表吴同学找了两个题目说有意思让我试一下,害,当天晚上没做出来,有时间了再看这题目,其实就是头插法,尾插法是正序,头插法就是反转了,代码附上,关键是第二题。
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
#include <cstddef>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}return Rs;}
};
链表内指定区间反转
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转。
这个题目首先我的想法就是把第一题反转的函数用上,然后把只需要截断反转再连接就可以了。我们使用示例{1,2,3,4,5},2,4。
第一种思路:
首先是找到需要反转的区间链表,
ListNode* dummyNode = new ListNode(-1);
dummyNode->next = head;ListNode* pre = dummyNode;
for(int i=0;i<m-1;i++){pre = pre->next;
}ListNode* rightNode = pre ;
for(int i=0;i<n-m+1;i++){rightNode = rightNode->next;
}ListNode* leftNode = pre->next;//leftNode = {2,3,4,5}
ListNode* cur = rightNode->next;//后置链表 cur = {5}//截断链表
pre->next=NULL;//前置链表截断 pre = {1}
rightNode->next=NULL;//后置链表截断 leftNode = {2,3,4}
反转函数:
ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}return Rs;
}
得到反转后的区间后,前置部分直接链接,后置部分通过遍历到反转区间链表的最后一个元素指向最后一部分。
ListNode* mid = ReverseList(leftNode);//mid = {4,3,2}pre->next = mid;
while (mid ->next)mid = mid -> next;
mid ->next = cur;
return dummyNode->next;
完整代码:
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
#include <ios>
#include <iostream>
using namespace std;
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param head ListNode类* @param m int整型* @param n int整型* @return ListNode类*/ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}return Rs;}ListNode* reverseBetween(ListNode* head, int m, int n) {// write code hereListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* pre = dummyNode;for(int i=0;i<m-1;i++){pre = pre->next;}ListNode* rightNode = pre ;for(int i=0;i<n-m+1;i++){rightNode = rightNode->next;}ListNode* leftNode = pre->next;ListNode* cur = rightNode->next;pre->next=NULL;rightNode->next=NULL;ListNode* mid = ReverseList(leftNode);pre->next = mid;while (mid ->next)mid = mid -> next;mid ->next = cur;return dummyNode->next;}
};
第二种思路:
第二种思路就是反转函数返回一个链表有点多此一举,只需要在反转函数里对链表进行操作即可。
反转函数:
void ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}
}
反转后:
//反转前 leftNode = {2,3,4} rightNode = {4}
ReverseList(leftNode);
//反转后 leftNode = {2} rightNode = {4,3,2}
pre->next = rightNode;
leftNode->next = cur;
return dummyNode->next;
完整代码:
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
#include <ios>
#include <iostream>
using namespace std;
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param head ListNode类* @param m int整型* @param n int整型* @return ListNode类*/void ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}}ListNode* reverseBetween(ListNode* head, int m, int n) {// write code hereListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* pre = dummyNode;for(int i=0;i<m-1;i++){pre = pre->next;}ListNode* rightNode = pre ;for(int i=0;i<n-m+1;i++){rightNode = rightNode->next;}ListNode* leftNode = pre->next;ListNode* cur = rightNode->next;pre->next=NULL;rightNode->next=NULL;ReverseList(leftNode);pre->next = rightNode;leftNode->next = cur;return dummyNode->next;}
};
链表介绍
链表(Linked List)是一种线性数据结构,其中的元素(通常称为节点)按顺序排列,每个节点包含两部分信息:存储数据的部分和指向下一个节点的指针或引用。链表中的每个节点通过指针连接在一起,因此它不需要在内存中连续存储。链表有几种常见的形式:
- 单向链表(Singly Linked List):每个节点只包含一个指向下一个节点的指针,链表是单向的,无法向后遍历。
- 双向链表(Doubly Linked List):每个节点包含两个指针,一个指向下一个节点,另一个指向前一个节点,因此可以双向遍历。
- 循环链表(Circular Linked List):链表的最后一个节点指向链表的第一个节点,形成一个环。
链表的优点:
-
动态内存分配:链表不需要预先定义大小,可以根据需要动态增长或缩小。
-
插入和删除操作:链表的插入和删除操作可以在常数时间内完成,特别是对于已知位置的节点。
链表的缺点: -
随机访问:由于链表的元素不在连续的内存位置,因此不能像数组一样通过索引进行随机访问,必须从头节点开始遍历。
链表广泛应用于实现队列、栈以及某些复杂数据结构,如图和哈希表的底层实现。