任務(wù)

第二章 鏈表part01

今日任務(wù)

● 鏈表理論基礎(chǔ)

● 203.移除鏈表元素

● 707.設(shè)計鏈表

● 206.反轉(zhuǎn)鏈表

詳細布置

鏈表理論基礎(chǔ)

建議：了解一下鏈接基礎(chǔ)，以及鏈表和數(shù)組的區(qū)別

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

203.移除鏈表元素

建議： 本題最關(guān)鍵是要理解 虛擬頭結(jié)點的使用技巧，這個對鏈表題目很重要。

題目鏈接/文章講解/視頻講解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

707.設(shè)計鏈表

建議： 這是一道考察 鏈表綜合操作的題目，不算容易，可以練一練 使用虛擬頭結(jié)點

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

206.反轉(zhuǎn)鏈表

建議先看我的視頻講解，視頻講解中對 反轉(zhuǎn)鏈表需要注意的點講的很清晰了，看完之后大家的疑惑基本都解決了。

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

鏈表定義

C++

// 單鏈表
struct ListNode {
    int val;  // 節(jié)點上存儲的元素
    ListNode *next;  // 指向下一個節(jié)點的指針
    ListNode(int x) : val(x), next(NULL) {}  // 節(jié)點的構(gòu)造函數(shù)
};
ListNode* head = new ListNode(5);

python

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

刪除-內(nèi)存釋放

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

image.png

203.移除鏈表元素

力扣題目鏈接(opens new window)

題意：刪除鏈表中等于給定值 val 的所有節(jié)點。

示例 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)：鏈表基礎(chǔ)操作| LeetCode：203.移除鏈表元素 (opens new window)

• 添加虛擬頭節(jié)點

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.設(shè)計鏈表

力扣題目鏈接(opens new window)

題意：

在鏈表類中實現(xiàn)這些功能：

• get(index)：獲取鏈表中第 index 個節(jié)點的值。如果索引無效，則返回-1。
• addAtHead(val)：在鏈表的第一個元素之前添加一個值為 val 的節(jié)點。插入后，新節(jié)點將成為鏈表的第一個節(jié)點。
• addAtTail(val)：將值為 val 的節(jié)點追加到鏈表的最后一個元素。
• addAtIndex(index,val)：在鏈表中的第 index 個節(jié)點之前添加值為 val 的節(jié)點。如果 index 等于鏈表的長度，則該節(jié)點將附加到鏈表的末尾。如果 index 大于鏈表長度，則不會插入節(jié)點。如果index小于0，則在頭部插入節(jié)點。
• deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個節(jié)點。

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.反轉(zhuǎn)鏈表

力扣題目鏈接(opens new window)

題意：反轉(zhuǎn)一個單鏈表。

示例: 輸入: 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;
    }
};