[代码随想录一刷&二刷] day3 链表

● 链表理论基础 ● 203.移除链表元素 ● 707.设计链表 ● 206.反转链表

链表理论基础

链表内存空间不连续，查询O(n),插入删除O(1)。

alt

移除链表元素

虚拟头节点

使用虚拟头结点避免删除链表头的情况单独讨论，虚拟头节点（哨兵节点）可以避免对链表空和头结点操作的单独讨论，遍历的时候正好也起到pre得到作用，注意操作是对cur->next，返回的是virtualHead->next,head有可能已经被删除了。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* virtualHead = new ListNode(-1);
        virtualHead->next = head;
        ListNode* cur = virtualHead;
        while(cur->next != nullptr) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return virtualHead->next;
    }
};

C#

public class Solution {
    public ListNode RemoveElements(ListNode head, int val) {
        ListNode virtualHead = new ListNode(-1);
        virtualHead.next = head;
        ListNode cur = virtualHead;
        while(cur.next != null) {
            if(cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return virtualHead.next;

    }
}

设计链表

链表数据结构的构建、在头和尾分别插入节点、在指定位置插入和删除元素或查询。

注意插入的索引范围是0-size, 删除的范围是0-size-1,应为插入会多一个空。

操作的是cur->next，cur要按虚拟头结点提前一位，才能保证能获取到第n个节点的前驱进行操作，插入注意先更新new->next = cur->next,再cur->next = new,避免后续索引的丢失

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

        struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };
    
    MyLinkedList() {
        virtualHead = new ListNode(0);
        size = 0;
    }
    
    int get(int index) {
        //printList() 
        if(index < 0 || index > size - 1) {
            return -1;
        }
        ListNode* cur = virtualHead->next;
        while(index --) {
            cur= cur->next; 
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = virtualHead->next;
        virtualHead->next = newNode;
        size++;
    }
    
    void addAtTail(int val) {
        ListNode* newNode = new ListNode(val);
        ListNode* cur;
        cur = virtualHead;
        while(cur->next != nullptr) {
            cur = cur->next;
        }
        cur->next = newNode;
        newNode->next = nullptr;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > size || index < 0) return;
        ListNode* newNode = new ListNode(val);
        ListNode * cur = virtualHead;
        while(index--) {
            cur = cur->next;
        }
        ListNode* tmp = cur->next;
        cur->next = newNode;
        newNode->next = tmp;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index > size - 1) {
            return;
        }
        ListNode * cur = virtualHead;
        while(index--) {
            cur = cur->next;
        }
        ListNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size--;
    }

    void printList() {
        ListNode* cur = virtualHead->next;
        while(cur != nullptr) {
            cout << cur->val;
        }
        cout << endl;
    }
private:
    int size;
    ListNode* virtualHead;
};

注意要维护size来使在指定Index插入，删除，获取是合法的，指针为空C+是nullptr，C+的结构体构造函数是ListNode(int val):val(val), next(nullptr)的形式。

C#

public class MyLinkedList {
    private ListNode1 virtualHead;
    private int size;
    public MyLinkedList() {
        virtualHead = new ListNode1(0);
        size = 0;
    }
    
    public int Get(int index) {
        if(index < 0 || index >= size) {
            return -1;
        }
        ListNode1 cur = virtualHead;
        while(index-- > 0) {
            cur = cur.next;
        }
        return cur.next.val;
    }
    
    public void AddAtHead(int val) {
        ListNode1 newNode = new ListNode1(val);
        newNode.next = virtualHead.next;
        virtualHead.next = newNode;
        size++;
    }
    
    public void AddAtTail(int val) {
        ListNode1 newNode = new ListNode1(val);
        ListNode1 cur = virtualHead;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
        size++;
    }
    
    public void AddAtIndex(int index, int val) {

        if(index < 0 || index > size) return;
        ListNode1 cur = virtualHead;
        ListNode1 newNode = new ListNode1(val);
        while(index-- > 0) {
            cur = cur.next;
        }
        ListNode1 tmp = cur.next;
        cur.next = newNode;
        newNode.next = tmp;
        size++;
    }
    
    public void DeleteAtIndex(int index) {
        if(index < 0 || index >= size) return;
        ListNode1 cur = virtualHead;
        while(index-- > 0) {
            cur = cur.next;
        }
        ListNode1 tmp = cur.next;
        cur.next = cur.next.next;
        size--;
    }
}
public class ListNode1 {
    public int val;
    public ListNode1 next;
    public ListNode1(int val, ListNode1 next = null) {
        this.val = val;
        this.next = next;
    }
}

反转链表

双指针

用一个pre指针储存前驱，注意每次反转是将当前节点的下一个指针指向前驱，先保存下一个节点，反转，再更新pre和cur。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* tmp;
        ListNode* pre = nullptr;
        while(cur != nullptr) {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

递归

注意递归的初始条件，返回条件为cur==null,pre和cur的更新通过调用子递归，思路和双指针一样。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverseNode(head, nullptr);
    }
    ListNode* reverseNode(ListNode* cur, ListNode * pre) {
        if(cur == nullptr) return pre;
        ListNode* tmp = cur->next;
        cur->next = pre;
        return reverseNode(tmp, cur);
    }
};

C#

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode cur = head;
        ListNode next;
        ListNode pre = null;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

二刷

删除链表

第一反应多写了个pre记录前驱节点，其实直接while条件往前放一层就可以避免，写一个指针就可以。

		ListNode* VirtualHead = new ListNode(-1);
		VirtualHead->next = head;
		ListNode* pre = VirtualHead;
		ListNode* cur = pre->next;
		while (cur != nullptr) {
			if (cur->val == val) {
				ListNode* temp = cur;
				pre->next = pre->next->next;
				delete temp;
				cur = pre->next;

			}
			else {
				pre = cur;
				cur = cur->next;
			}
		}
		return VirtualHead->next;

设计链表

还是开size记录一下链表的长度比较方便判断index是否合法，注意插入的位置比删除多一个。

class MyLinkedList {
public:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int val) : val(val), next(nullptr) { }
    };
    MyLinkedList() {
        virtualHead = new ListNode(-1);
        size = 0;
    }

    int get(int index) {
        if (index < 0 || index >= size) return -1;
        ListNode* cur = virtualHead;
        if (cur == nullptr) return -1;
        while (index--) {
            cur = cur->next;
        }
        return cur->next->val;
    }

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

    void addAtTail(int val) {
        ListNode* cur = virtualHead;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        ListNode* newNode = new ListNode(val);
        cur->next = newNode;
        size++;
    }

    void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        ListNode* cur = virtualHead;
        while (index--) {
            cur = cur->next;
        }
        ListNode* newNode = new ListNode(val);
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        ListNode* cur = virtualHead;
        while (index--) {
            cur = cur->next;
        }
        ListNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        size--;
    }
private:
    ListNode* virtualHead;
    int size;
};

反转链表

不用虚拟头节点，双指针用pre储存前驱，先存下个节点，再反转当前节点指向前驱，重复处理下个节点，秒了。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

剑指&代码随想录文章被收录于专栏

刷题记录~~~