203. 移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/solutions/2772075/203-yi-chu-lian-biao-yuan-su-by-joker-ek-kyhf

707. 设计链表

https://leetcode.cn/problems/design-linked-list/solutions/2772214/707-she-ji-lian-biao-by-joker-ek4-lbig

思路：

因为有dummyHead，因此代码就花了许多，不用考虑第一个借点的情况。
注意 void addAtIndex(int index, int val)
void deleteAtIndex(int index)的时候，找到下标index - 1节点的时候，要用如下代码

1
2
3
4
5
LinkedNode *curr = _dummyHead;
for (int i = -1; i < index - 1; i++)
{
curr = curr->next;
}

206. 反转链表

思路：

这一题不用dummyHead会方便一些

https://leetcode.cn/problems/reverse-linked-list/solutions/2771061/206-fan-zhuan-lian-biao-by-joker-ek4-lm6d

反转单链表

1
2
3
Node* reverse(Node* list);
输入: 1 --> 2 --> 3
输出: 3 --> 2 --> 1

反转链表都是不要创建额外节点的，不需要额外内存空间，直接在原来链表上进行反转

思路1：头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
Node* prev = NULL;
Node* curr = list;
while(curr){
	//保留下一个节点
		Node* currNext = curr->next;
	//反转curr借点
	curr->next = prev;
	//跟新prev，curr
	prev = curr;
	curr = currNext;
}
// curr == NULL的时候循环结束
list = prev;//prev这个时候指向第一个节点

时间复杂度：O(n)

空间复杂度：O(1)

迭代实现
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //迭代
        ListNode* prev = NULL;
        ListNode* curr = head;
        while(curr){
            ListNode* currNext = curr->next;
            curr->next = prev;
            prev = curr;
            curr = currNext;
        }
        head = prev;
        return head; 
    }
};

思路2：递归

类似于数学归纳法：假设我已经实现了反转n - 1个结点（成立），那么如果在已经实现反转n - 1个节点的基础上，反转 n 个节点

边界条件:只有一个借点或者是空链表（类似于数学归纳法的归纳奠基，k = 0成立，k = 1成立。在假设k = n - 1成立，求证明k = n也成立

1
list == NULL || list->next == NULL

递归公式：

1
2
3
4
Node* head = reverse(list->next);//相当于假设k = n - 1成立，接下来只要证明k = n也成立
list->next->next = list;
list->next = NULL;

时间复杂度：O(n)

空间复杂度：O(n)

递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //递归
        //边界条件
        if(head == NULL || head->next == NULL) return head;
        //递归公式
        ListNode* headnew = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return headnew;

    }
};