Day3 | 203.移除链表元素 | 707.设计链表 |.反转链表

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路：通过一个虚拟头结点，遍历链表，删除和val相等的节点。注意删除的时候不要移动head，因为可能下一个也需要删除

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    // 思路：通过一个虚拟头结点，遍历链表，删除和val相等的节点
    dummy := &ListNode{}
    dummy.Next = head

    head = dummy

    for head.Next != nil {
        if head.Next.Val == val {
            head.Next = head.Next.Next
        }else {
            head = head.Next
        }
    }

    return dummy.Next
}

C++实现

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = dummy;
        while(cur->next != NULL) {
            if (cur->next->val == val) {
                ListNode* temp = cur->next;
                cur->next = cur->next->next;	// 最后指向空
                delete temp;
            }else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

理解：虚拟头结点的使用

707. 设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

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

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

class MyLinkedList {

public:
    struct ListNode {
        int val;
        ListNode * next;
        ListNode(int val):val(val), next(nullptr){}
    };

    MyLinkedList() {
        // 虚拟 头结点
        dummyHead = new ListNode(-1);
        m_size = 0;
    }
    
    int get(int index) {
        if(index >= m_size || index < 0) return -1;
        ListNode * cur = dummyHead->next;
        while(index --) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        addAtIndex(0, val);
        // ListNode * ndoe = new ListNode(val);
        // ndoe->next = dummyHead->next;
        // dummyHead->next = ndoe;
        // m_size ++;
    }
    
    void addAtTail(int val) {
        addAtIndex(m_size, val);
        // ListNode * node = new ListNode(val);
        // ListNode * cur = dummyHead;
        // while(cur->next) cur = cur->next;
        // cur->next = node;
        // m_size ++;
    }
    // 插入 在index之前插入
    void addAtIndex(int index, int val) {
        if(index > m_size) return;
        if(index < 0) index = 0;

        ListNode * cur = dummyHead;
        while(index -- ) {
            cur = cur->next;
        }
        ListNode * node = new ListNode(val);
        node->next = cur->next;
        cur->next = node;
        m_size ++;
    }
    
    void deleteAtIndex(int index) {
        if(index >= m_size || index < 0) return;
        ListNode * cur = dummyHead;
        while(index --) {
            cur = cur->next;
        }
        // 删除当前结点
        ListNode * tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        m_size --;
    }
private:
    ListNode * dummyHead;
    int m_size;
};

/**
 * 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);
 */

理解：注意几个问题

• 变量的定义在私有成员中
• addAtIndex, index的条件是可以等于m_size的，表示在最后插入

206. 反转链表

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

思路：将节点的后一个节点指向前一个节点。注意pre一定不要初始化，不然会值为0

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    // 思路：将节点的后一个节点指向前一个节点
    if head == nil {
        return nil
    }
    var pre *ListNode

    for head != nil {
        next := head.Next
        head.Next = pre
        pre = head
        head = next
    }
    return pre
}

C++实现

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 之所以为空，是因为第一个指向的是空
        ListNode * pre = nullptr;
        ListNode * next = nullptr;
        while(head) {
            // 下一个结点改变了，需要提前保存下来
            next = head->next;
            // 将当前结点的next指针 指向上一个节点
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
};

理解：循环结束的条件是头结点不为空。