代码随想录|Day 3|2023.7.28|链表part01

今日内容：链表理论基础，203.移除链表元素，707.设计链表，206.反转链表

文章链接： 代码随想录

​题目链接：203. 移除链表元素 ，707. 设计链表 ，206.反转链表

1.链表理论基础

单链表：

双链表：循环链表：

链表的题目以单链表居多，其特性和数组等类型的区别在于节点的指向性。每个节点包含一个val，同时也指向下一个节点，这意味着和数组依靠索引去引用不同，对于某个节点的信息获取往往需要上一个节点来指向。这就涉及到许多常见的链表操作，比如删除和添加可以通过改变指向来实现，再比如对于头结点的处理往往可以建立虚拟头结点来实现。同时其长度也可以随着操作而不断改变，这和数组有很大的区别。
链表与数组：

定义：

// 单链表定义
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

2.203移除链表元素

题目简单，利用链表的性质，要移除一个元素只需要将其跳过即可。注意的点在于，由于可能需要删除头结点，所以需要建立虚拟头结点来完成连接。同时循环条件也需要注意，避免报错。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* x = new ListNode(0);
        x->next = head;
        ListNode* y = x;
        while (y->next) {
            if(y->next->val == val) {
                y->next = y->next->next;
            } else {
                y = y->next;
            }
        }
        return x->next;
    }
};

python版：

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        x = ListNode(0, head)
        y = x
        while y.next:
            if y.next.val == val:
                y.next = y.next.next
            else:
                y = y.next
        return x.next

3.707 设计链表

这道题相对比较综合，涉及了链表的定义已经常见操作。因为我是C++和python都练习，所以感触比较大的是二者对于链表的操作还是有较大差距的。C++创建新节点的时候涉及new动态分配，而python可以直接创建。同时这道题也再一次说明了虚拟头结点的好处。完成这道题也对理解单链表有很大帮助。

class MyLinkedList {
public:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int val) : val(val), next(NULL) {}
    };
    
    MyLinkedList() {
        size = 0;
        dummy = new ListNode(0);
    }

    int get(int index) {
        if (index < 0 || index >= size)
            return -1;
        ListNode* cur = dummy->next;
        for (int i = 0; i < index; i++)
            cur = cur->next;
        return cur->val;
    }

    void addAtHead(int val) {
        ListNode* newhead = new ListNode(val);
        newhead->next = dummy->next;
        dummy->next = newhead;
        size++;
    }

    void addAtTail(int val) {
        ListNode* cur = dummy;
        while (cur->next != NULL)
            cur = cur->next;
        ListNode* addNode = new ListNode(val);
        cur->next = addNode;
        size++;
    }

    void addAtIndex(int index, int val) {
        if (index < 0 || index > size)
            return;
        ListNode* cur = dummy;
        ListNode* addNode = new ListNode(val);
        for (int i = 0; i < index; i++)
            cur = cur->next;
        addNode->next = cur->next;
        cur->next = addNode;
        size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size)
            return;
        ListNode* cur = dummy;
        for (int i = 0; i < index; i++)
            cur = cur->next;
        if (cur->next != NULL) {
            ListNode* temp = cur->next;
            cur->next = cur->next->next;
            delete temp;
            size--;
        }
    }

private:
    ListNode* dummy;
    int size;
};

python版：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList:

    def __init__(self):
        self.size = 0
        self.dummy = ListNode(0)

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        cur = self.dummy.next
        for i in range(index):
            cur = cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        self.dummy.next = ListNode(val,self.dummy.next)
        self.size += 1

    def addAtTail(self, val: int) -> None:
        cur = self.dummy
        while cur.next:
            cur = cur.next
        cur.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return -1
        cur = self.dummy
        for i in range(index):
            cur = cur.next
        cur.next = ListNode(val,cur.next)
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return -1
        cur = self.dummy
        for i in range(index):
            cur = cur.next
        cur.next = cur.next.next
        self.size -= 1

# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

4.206反转链表

这道题可以说是非常经典，算是链表必考题。所谓反转就是要改变指向，而不是新建链表。要将头变成尾，尾变成头。因此对于相邻节点，逆转指向即可，同时通过中间量保存下一个节点来实现循环，直到最后一个节点。

动态示意图：

/**
 * 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* pre = NULL;
        ListNode* cur = head;
        while(cur){
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        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]:
        pre = None
        cur = head
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

总之链表的题目都是建立在对数据结构的理解上的，应该跳出对数组的理解，抓住特性去思考题目。文章来源地址https://uudwc.com/A/DyMyk