代码随想录打卡 Day 2
1.链表的定义与操作
链表作为基本的数据结构类型，其主要形式有三种:
-
单链表
-
双链表
-
循环链表
由于刷代码题平时在OJ上默认定义已经给出，可以直接使用。而在面试/机试时，一般需要需要自己手写链表。因此，正确写出链表的定义是非常有必要的。一个单链表的定义如下所示:
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(nullptr){} //节点的构造函数
};
其中，注意到，第三行给出了一个构造函数，通过这个构造函数，我们可以对一个新节点的val变量直接赋值。
链表的基本操作包括了：
- 删除节点
- 添加节点
- 查询链表内元素(包括按照
val值和索引值)
相比较数组，链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。
2.链表常见的6个操作
leetcode题号:707.设计链表
【题目描述】
设计一个链表类，实现六个接口:
- 获取链表第
index个节点的值(按索引查询) - 在链表的最前面插入一个节点(头插法)
- 在链表的最后面插入一个节点(尾插法)
- 在链表的第
index个节点插入一个节点(按索引插入) - 删除链表的第
index个节点(按索引删除) - 打印当前链表
【题目分析】
该题是练习链表操作的一道非常好的题目，六个结构覆盖了链表的常见操作，其代码如下:
class MyLinkedList {
public:
struct Node {
int val;
Node* next;
Node(int x) : val(x), next(NULL) {}
};
private:
Node* _dummyhead; //设置一个伪头指针，方便后续操作
int _size; // _size表示链表元素个数
MyLinkedList() { //构造函数
_dummyhead = new Node(0);
_size = 0;
}
int get(int index) { //按索引查询元素
if(index > _size -1 || index < 0)
return -1;
Node* cur=_dummyhead->next;
while (index--){
cur=cur->next;
}
return cur->val;
}
void addAtHead(int val){ //头插法
Node* newnode = new Node(val);
newnode->next = _dummyhead->next;
_dummyhead->next = newnode;
_size++;
}
void addAtTail(int val) { //尾插法
Node* newnode =new Node(val);
Node* cur=_dummyhead;
while (cur->next != NULL){
cur=cur->next;
}
cur->next=newnode;
_size++;
}
void addAtIndex(int index, int val) { //按索引插入
if(index>_size) return;
if(index<0) index=0;
Node* newnode = new Node(val);
Node* cur=_dummyhead;
while(index--){
cur=cur->next;
}
newnode->next=cur->next;
cur->next=newnode;
_size++;
}
void deleteAtIndex(int index) { //按索引删除
if(index>=_size || index<0) return;
Node* cur=_dummyhead;
while(index--){
cur=cur->next;
}
Node* tmp=cur->next;
cur->next=cur->next->next;
delete tmp;
tmp=nullptr;
_size--;
}
void printList(){ //打印链表
Node* cur=_dummyhead;
while (cur->next != NULL){
cout<<cur->next->val<<" ";
cur=cur->next;
}
cout<<endl;
}
};
3.利用伪头节点(dummy_Head)来简化操作
在单链表中，删除头节点与删除其他节点的操作不一样，除了共同的释放内存和指针移动之外，还需要移动头指针。通过设置一个伪头节点，最后将dummy_Head->next设置为新的头节点即可。
以leetcode203题移除链表元素为例，设置伪头节点可以方便处理待处理元素为头节点的情况。
本题的代码如下:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(-1); //伪头节点的设置
dummy->next = head;
ListNode* cur = dummy;
while(cur->next!=NULL){
if(cur->next->val == val){
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}else{
cur = cur->next;
}
}
head = dummy->next; //设置新的头节点
delete dummy; //删除伪头节点
return head;
}
4.链表的反转
leetcode题号:206.反转列表
【题目描述】
反转一个单链表，要求不能申请额外的内存空间
【题目分析】
反转链表是链表操作中的一个重要思路，这里使用双指针法和递归法来实现。对于双指针发，只需要改变next指针的指向，不需要重新定义一个新的链表。
双指针法
双指针法的思想是定义一个cur指针和prev指针，分别进行遍历，并且使用nxt指针保存下一个指针，便于遍历。
双指针法的代码如下所示:
ListNode* reverseList(ListNode *head) {
if (head == NULL || head->next == NULL) { //对链表只有至多一个元素的边界条件处理
return head;
}
ListNode *p = head->next;
ListNode *prev = head;
ListNode *nxt= NULL; //nct指针保存p所指的下一个结点
while(p!=NULL){ //遍历
nxt = p->next;
p->next = prev;
prev = p;
p = nxt;
}
return prev;
}
递归法
递归法的思路实质上与双指针法的思路一致，但是递归法的代码较为抽象，比较难写。代码如下所示:
ListNode* reverse(ListNode * pre, ListNode * cur) {
if (cur == NULL) return pre;
ListNode * nxt = cur->next;
cur->next = pre;
//如下递归的算法，实质上完成了：
//pre=cur;
//cur=temp;
return reverse(cur, nxt);
}
ListNode* reverseList(ListNode *head) {
//与双指针法的初始化逻辑一致
return reverse(NULL, head);
}
5.双指针法在链表中的应用
1）删除倒数第N个节点
【基本思路】
如果要删除倒数第N个节点，可以先让快指针fast移动N步，然后让fast和slow同时移动，删除slow所在的节点即可。
删除链表倒数第N个节点又应该使用伪头节点，让slow节点指向待删除节点前一个节点。因此，可以让fast先动一步，然后让fast移动N步，最后让fast和slow同时移动一步。
基于以上思路，本题的代码如下所示:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0, head);
dummyHead->next = head; //伪头节点设置
ListNode* fast = dummyHead;
ListNode* slow = dummyHead;
while(n-- && fast->next != nullptr) { //fast移动N步
fast = fast->next;
}
fast = fast->next; //需要让slow指向要删除节点的前一个节点
while(fast!=NULL){ //fast与slow同时移动一步
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummyHead->next;
}
对快慢指针进行移动方法调整，就可以获得单链表的中间节点。
2）判断链表是否有环
【基本思路】
通过快慢指针法，分别定义fast与slow指针，从头节点出发，fast移动两步，slow移动一步，若fast与slow相遇，则说明有环，否则则无环。
但是，如果要寻找到环的入口，则是一个比较困难的问题。在这里，我们假设从头节点到环的入口的节点数为$x$，环形入口节点到fast与slow节点相遇节点数为$y$。从相遇节点再到环形入口节点书为$z$.
那么，相遇时,slow走过了$(x+y)$个节点，fast走过了$2(x+y)=x+y+n*(y+z)$个节点，其中$n$为fast指针与slow相遇时已经走过的圈数。
通过化简，得到
$$x=(n-1)(y+z)+z$$,
$$x+y=n(y+z)$$
此时，可以在相遇节点处定义一个指针index1,在头节点处定义index2，让两个指针同时移动一步，两者相遇的位置即为环形入口的起点。
根据以上的思路，可以整理出本题的解
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { //找到环后的处理
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}
3）判断两个链表的共同后缀
【基本思路】
两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。题目数据保证整个链式结构中不存在环。
本题可以通过先遍历A，B链表的长度，再使用双指针法进行操作。需要注意的是，交错链表并非数值相等，而是指针相等。
基于以上思考，可以给出如下的算法:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == NULL || headB == NULL) {
return NULL;
}
ListNode *pA = headA, *pB = headB;
int lenA = 0, lenB = 0;
while(pA!=NULL){
lenA++;
pA = pA->next;
}
while(pB!=NULL){
lenB++;
pB = pB->next;
}
pA = headA;pB = headB;
if (lenB > lenA) {
swap(lenA, lenB);
swap(pA, pB);
}//保证headA是长的,便于算法的求解
int gap = lenA - lenB;//计算两者长度插值，为接下来使用快慢指针法做准备
while (gap--){
pA = pA->next;
}
while (pA != NULL) {
if(pA == pB) return pA;
pA = pA->next;
pB = pB->next;
}
return NULL;
}
6. 总结
对于以单链表为基本数据结构的算法题，主要的技巧就是伪头节点，双指针，以及反转链表。
- 伪头节点:其主要作用时简化链表的边界条件，简化操作，并保持链表结构的一致性。
- 双指针法:通过快慢指针的方法，可以快速查找中间节点，倒数K个节点等特殊节点，以及探测链表中的环。
- 反转链表:通过设置
prev,curr,next三个指针，可以将链表进行反转操作，便于判断回文等操作的实现。