复习Day05：链表part01:203.移除链表元素、707.设计链表、206.反转链表、234. 回文链表

之前的blog链接：https://blog.csdn.net/weixin_43303286/article/details/131700482?spm=1001.2014.3001.5501

我用的方法是在leetcode再过一遍例题，明显会的就复制粘贴，之前没写出来就重写，然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用CLion了，使用leetcode自带模拟面试环境。

今天开始链表章节的复习了，不能在数组花太长时间，后面还有专门的双指针和动态规划章节的复习，被归到数组章节中，到那时候再复习。

203. 移除链表元素

没什么好说的，删除值为val的节点，遍历一遍删就行了，注意设置虚拟头节点dummy，以及删除链表的操作C++是delete p。

707.设计链表

涵盖了链表的一系列相关操作，包括数据结构的设计：

class MyLinkedList {

public:  
struct ListNode{  
int val;  
ListNode* next;  
ListNode(int x):val(x),next(NULL){};//构造函数  
};  
//初始化链表,  
MyLinkedList() {  
_dummy = new ListNode(0);  
_size = 0;  
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

这里注意有两个，一个是MyLinkedList类，一个是类中的数据结构ListNode，MyLinkedList()是初始化函数。

206.反转链表

这里使用双指针，用pre节点保存cur的前一个节点。(准确来说还有一个暂时的指针tmp用来保存cur的后一个节点）

（思路很清晰，还是还是记不住，还是要多刷刷，链表的题目就是思路简单但像做出来就ac很难）

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

 

示例 1：


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


输入：head = [1,2]
输出：false
1
2
3
4
5
6
7
8
9
10
11
12
13
14

之前有做过判断回文串的题目，但在这里不适用，使用的是双指针法，因为单向链表是不能倒着遍历的，因此考虑别的方法。

借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表

链表兼具递归结构，树结构不过是链表的衍生。那么，链表其实也可以有前序遍历和后序遍历：

void traverse(ListNode* head) {
    // 前序遍历代码
    traverse(head->next);
    // 后序遍历代码
}
1
2
3
4
5

这个框架有什么指导意义呢？如果我想正序打印链表中的 val 值，可以在前序遍历位置写代码；反之，如果想倒序遍历链表，就可以在后序遍历位置操作：

/* 倒序打印单链表中的元素值 */
void traverse(ListNode* head) {
    if (head == NULL) return;
    traverse(head->next);
    // 后序遍历代码
    print(head->val);
}
1
2
3
4
5
6
7

但这种方法由于引入了栈，时间和空间复杂度都是O(N)，还可以借助双指针先找到链表的中点，再进行反转比较，这里就不纠结细节了，具体代码如下，三刷再来看：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *fast = head, *slow = head;
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
        }
        if(fast != nullptr){//链表的长度为奇数
            slow = slow->next;
        }
        ListNode* left  = head;
        ListNode* right = reverse(slow);
        while (right != nullptr) {
        if (left->val != right->val)
            return false;
        left = left->next;
        right = right->next;
    }
    
        return true;


    }

    //反转链表的函数
    ListNode* reverse(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur != nullptr) {
        ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

（可以看到这里的reverse函数和我们上一题的函数是一模一样的）

这里判断的条件为什么是while (right != nullptr) ：因为left指向的是head，而right指向的是链表重点，因为肯定right短一些先到头，因此循环由right控制。