刷题笔记3 ｜ 203. 移除链表元素、707设计链表，206.反转链表

目录

203. 移除链表元素

707、设计链表

206.反转链表

---

203. 移除链表元素

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

1、感觉最好的写法还是设置虚拟结点。

2、删除中间结点的操作是 cur->next = cur->next->next，即改变前一结点的指向，记住C/C++，需要释放空间。删除头结点的操作是head = head->next。

3、设置好虚拟结点后，就将删除结点的操作统一为了cur->next = cur->next->next

C++版本

/*** 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* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;while(cur->next!=nullptr){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;}
};

Python版本：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:dummyHead = ListNode()dummyHead.next = headcur = dummyHeadwhile(cur.next!=None):if cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.nextreturn dummyHead.next

707、设计链表

在链表类中实现这些功能：

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

这个题挺简单的，还是按照设置虚拟结点，主要是为了方便deleteAtIndex。

另外需要注意的是，题目中index的范围是从0开始的，也就是说index=0的结点代表head结点。所以index的范围是[0,size)，注意是开区间。

        while(index--){ // 如果--index 就会陷入死循环
            cur = cur->next;
        }

于是这条语句就可以实现跳转到对应结点。

C++版本：

class MyLinkedList {
public:// 定义链表节点结构体struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};// 初始化链表MyLinkedList() {_dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点_size = 0;}// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点int get(int index) {if (index > (_size - 1) || index < 0) {return -1;}LinkedNode* cur = _dummyHead->next;while(index--){ // 如果--index 就会陷入死循环cur = cur->next;}return cur->val;}// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}// 在链表最后面添加一个节点void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(cur->next != nullptr){cur = cur->next;}cur->next = newNode;_size++;}// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度，则返回空// 如果index小于0，则在头部插入节点void addAtIndex(int index, int val) {if(index > _size) return;if(index < 0) index = 0;        LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的void deleteAtIndex(int index) {if (index >= _size || index < 0) {return;}LinkedNode* cur = _dummyHead;while(index--) {cur = cur ->next;}LinkedNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;_size--;}// 打印链表void printLinkedList() {LinkedNode* cur = _dummyHead;while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}
private:int _size;LinkedNode* _dummyHead;};

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

 

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

 解法一：

把链表值保存下来，再重新组织链表。缺点就是，对空间复杂度要求高，O(n)。

/*** 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) {vector<int> nums;ListNode* cur = head;while(cur != nullptr){// cout<<cur->val<<endl;nums.push_back(cur->val);cur = cur->next;}reverse(nums.begin(),nums.end());ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur1 = dummyHead;for(int i=0; i<nums.size(); i++){// cout << nums[i] << endl;cur1->next->val = nums[i];cur1 = cur1->next; }cur1->next = nullptr;head = dummyHead->next;delete dummyHead;return head;}
};

解法二、双指针法

整个逻辑就是： 

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

/*** 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* cur = head;ListNode* pre = nullptr;while(cur!=nullptr){ListNode* tmp = cur;   // 保存当前cur指向的结点cur = cur->next;        // 向后移动curtmp->next = pre;        // 改变tmp的指向pre = tmp;            //向前移动pre}return pre;}
};

Python版本：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:cur = headpre = Nonewhile(cur != None):tmp = curcur = cur.nexttmp.next = prepre = tmpreturn pre