任务

第二章 链表part01

今日任务

● 链表理论基础

● 203.移除链表元素

● 707.设计链表

● 206.反转链表

详细布置

链表理论基础

建议：了解一下链接基础，以及链表和数组的区别

文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

203.移除链表元素

建议： 本题最关键是要理解 虚拟头结点的使用技巧，这个对链表题目很重要。

题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

707.设计链表

建议： 这是一道考察 链表综合操作的题目，不算容易，可以练一练 使用虚拟头结点

题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

206.反转链表

建议先看我的视频讲解，视频讲解中对 反转链表需要注意的点讲的很清晰了，看完之后大家的疑惑基本都解决了。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

链表定义

C++

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

python

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

删除-内存释放

https://www.cnblogs.com/carle-09/p/11554998.html

image.png

203.移除链表元素

力扣题目链接(opens new window)

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

《代码随想录》算法视频公开课 (opens new window)：链表基础操作| LeetCode：203.移除链表元素 (opens new window)

• 添加虚拟头节点

python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        dummy_head = ListNode(next = head)
        p = dummy_head
        while(p.next) :
            if(p.next.val == val) :
                p.next = p.next.next
            else:
                p = p.next
        return dummy_head.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* dummy_head = new ListNode();
        dummy_head->next = head;
        ListNode* cur = dummy_head;
        while(cur->next != nullptr) {
            if (cur->next->val == val) {
                ListNode* p = cur->next;
                cur->next = cur->next->next;
                p->next = nullptr;
                delete p;
            } else {
                cur = cur->next;
            }
        }
        return dummy_head->next;
    }
};

707.设计链表

力扣题目链接(opens new window)

题意：

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

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

python

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

class MyLinkedList(object):

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

    def get(self, index):
        """
        :type index: int
        :rtype: int
        """
        if (index >= self.size or index < 0 ) :
            return -1;

        cur = self.dummy_head.next
        for i in range(index):
            cur = cur.next
        return cur.val
        
    def addAtHead(self, val):
        """
        :type val: int
        :rtype: None
        """
        p = ListNode(val, self.dummy_head.next)
        self.dummy_head.next = p
        self.size += 1

    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        cur = self.dummy_head
        while(cur.next) :
            cur = cur.next
        cur.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        if (index < 0 or index > self.size) :
            return
        cur = self.dummy_head
        for i in range(index) :
            cur = cur.next
        cur.next = LisNode(val, cur.next)
        self.size += 1

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

C++

class MyLinkedList {
public:
    struct LinkNode {
        int val;
        LinkNode* next;
        LinkNode(int val) : val(val), next(nullptr) {}
    };

    MyLinkedList() {
        _size = 0;
        _dummyHead = new LinkNode(0);
    }
    
    int get(int index) {
        if(index < 0 || index >= _size){
            return -1;
        }
        LinkNode* cur = _dummyHead;
        for(int i = 0; i <= index; i++) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkNode* a = new LinkNode(val);
        a->next = _dummyHead->next;
        _dummyHead->next = a;
        _size += 1;
    }
    
    void addAtTail(int val) {
        LinkNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = new LinkNode(val);
        _size += 1;
    }
    
    void addAtIndex(int index, int val) {
        if(index < 0 || index > _size){
            return ;
        }
        LinkNode* cur = _dummyHead;
        for(int i = 0; i < index; i++) {
            cur = cur->next;
        }
        LinkNode* a = new LinkNode(val);
        a->next = cur -> next;
        cur -> next = a;
        _size += 1;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index >= _size) {
            return;
        }
        LinkNode* cur = _dummyHead;
        for(int i = 0; i < index; i++) {
            cur = cur->next;
        }
        LinkNode* d = cur->next;
        cur->next = cur->next->next;
        delete d;
        _size -= 1;
    }
private:
    int _size;
    LinkNode* _dummyHead;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206.反转链表

力扣题目链接(opens new window)

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy_head = ListNode()
        cur = head
        while(cur) :
            n = cur.next
            cur.next = dummy_head.next
            dummy_head.next = cur
            cur = n
        return dummy_head.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* reverseList(ListNode* head) {
        ListNode* dummyHead = new ListNode();
        ListNode* cur = head;
        while(cur) {
            ListNode* n = cur->next;
            cur->next = dummyHead->next;
            dummyHead->next = cur;
            cur = n;
        }
        return dummyHead->next;
    }
};