LeetCode练习——707.设计链表（C++）

杨哥学编程

2219人浏览 · 2024-10-14 01:06:08

杨哥学编程 · 2024-10-14 01:06:08 发布

LeetCode练习——707.设计链表（C++）

题目链接
题目描述
解题思路
- 单链表的设计
- 双链表的设计
总结

题目链接

设计链表

题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性： $v a l$ 和 $n e x t$ 。 $v a l$ 是当前节点的值， $n e x t$ 是指向下一个节点的指针 $/$ 引用。
如果是双向链表，则还需要属性 $p re v$ 以指示链表中的上一个节点。假设链表中的所有节点下标从 $0$ 开始。

实现 $M y L ink e d L i s t$ 类：

$M y L ink e d L i s t ()$ 初始化 $M y L ink e d L i s t$ 对象。
$int\ get(int\ index)$ 获取链表中下标为 $in d e x$ 的节点的值。如果下标无效，则返回 $- 1$ 。
$void\ addAtHead(int\ val)$ 将一个值为 $v a l$ 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
$void\ addAtTail(int\ val)$ 将一个值为 $v a l$ 的节点追加到链表中作为链表的最后一个元素。
$void\ addAtIndex(int\ index,\ int\ val)$ 将一个值为 $v a l$ 的节点插入到链表中下标为 $in d e x$ 的节点之前。如果 $in d e x$ 等于链表的长度，那么该节点会被追加到链表的末尾。如果 $in d e x$ 比长度更大，该节点将不会插入到链表中。
$void\ deleteAtIndex(int\ index)$ 如果下标有效，则删除链表中下标为 $in d e x$ 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

$0 <= in d e x, v a l <= 1000$
请不要使用内置的 $L ink e d L i s t$ 库。
调用 $g e t$ 、 $a dd A t He a d$ 、 $a dd A tT ai l$ 、 $a dd A t I n d e x$ 和 $d e l e t e A t I n d e x$ 的次数不超过 $2000$ 。

解题思路

这个题目要求我们实现设计一个链表（链表的下标从0开始），实现链表的 $5$ 个接口：

获取链表下表为 $in d e x$ 的结点的值
在头结点之前插入一个结点
在链表的最后插入一个结点
在指定位置插入一个结点
删除下表为 $in d e x$ 的结点
对于这个题，可以选择设计一个单链表，也可以选择实现一个双链表。

单链表的设计

单链表的每个结点除了数据区域外，还有有一个指针区域用来指向下一个结点。

单链表结构
结点结构：

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

插入结点：

// 假设要在p节点的后面插入一个q结点
q->next = p->next;
p->next = q;

插入结点

删除结点：

// 假设p是要删除的结点的前一个结点
p->next = p->next->next;

删除结点

不用虚拟头结点：

class MyLinkedList {
public:
	// 构造函数，初始化链表
	MyLinkedList() {
		head = nullptr;
		length = 0;
	}
	
	int get(int index) {
		// 下标无效，返回-1
		if (index < 0 || index >= length)
			return -1;
		ListNode* now = head;
		// 搜索链表中下标为index的结点
		while (index) {
			now = now->next;
			index--;
		}
		// 返回结点的值
		return now->val;
	}

	void addAtHead(int val) {
		ListNode* p = new ListNode(val, head);
		// 在头结点之前插入新节点后，新节点将作为新的头结点
		head = p;
		// 链表中每插入一个结点，链表的长度就增加1
		length++;
	}

	void addAtTail(int val) {
		// 链表为空时，在链表的最后插入结点的操作和在头部插入结点的操作一样的
		if (!head)
            addAtHead(val);
        else {
            ListNode* p = head;
            // 定位到最后一个结点
            while (p->next) {
                p = p->next;
            }
            ListNode* adder = new ListNode(val);
            // 直接让最后一个结点的next指针指向新结点
            p->next = adder;
            // 链表中每插入一个结点，链表的长度就增加1
            length++;
        }
	}

	void addAtIndex(int index, int val) {
		// 无效下标，直接结束
		if (index < 0 || index > length)
            return;
        // index为0的时候，直接在头部插入
        if (index == 0)
            addAtHead(val);
        // index和链表的长度相等时，在链表的最后插入结点
        else if (index == length)
            addAtTail(val);
        else {
        	// 搜索到下标为index结点的前一个结点
            ListNode* now = head;
            while (index - 1) {
                now = now->next;
                index--;
            }
            // 执行插入操作
            ListNode* p = new ListNode(val, now->next);
            now->next = p;
            length++;
        }
	}

	void deleteAtIndex(int index) {
		// 链表为空
		if (!head)
            return;
		// 无效下标
        if (index < 0 || index >= length)
            return;
        // 删除头结点
        if (index == 0) {
            head = head->next;
        }
        // 删除非头结点
        else {
            ListNode* p = head;
            // 搜索到要删除的结点的前一个结点
            while (index - 1) {
                p = p->next;
                index--;
            }
            p->next = p->next->next;
        }
        // 从链表中删除一个结点，链表的长度减1
        length--;
	}

private:
	int length; // 链表的长度
	ListNode* head; // 头结点
};

使用虚拟头结点：

class MyLinkedList {
public:
    MyLinkedList() {
        virtualHead = new ListNode(0);
        length = 0;
    }
    
    int get(int index) {
        if (index < 0 || index >= length)
            return -1;
        // 从虚拟头结点下面一个结点（实际地=的头结点）开始搜索
        ListNode* p = virtualHead->next;
        while (index) {
            p = p->next;
            index--;
        }
        return p->val;
    }
    
    // 可以直接插入到虚拟头结点的后面
    void addAtHead(int val) {
        ListNode* p = new ListNode(val, virtualHead->next);
        virtualHead->next = p;
        length++;
    }
    
    void addAtTail(int val) {
        ListNode* now = virtualHead;
        while (now->next) {
            now = now->next;
        }
        ListNode* p = new ListNode(val);
        now->next = p;
        length++;
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0 || index > length)
            return;
        if (index == length)
            addAtTail(val);
        else {
            ListNode* p = virtualHead;
            while (index) {
                p = p->next;
                index--;
            }
            p->next = new ListNode(val, p->next);
            length++;
        }
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= length)
            return;
        ListNode* p = virtualHead;
        while (index) {
            p = p->next;
            index--;
        }
        p->next = p->next->next;
        length--;
    }
private:
    int length; // 链表的长度
    ListNode* virtualHead; // 虚拟头结点，真正的头结点是虚拟头结点的下一个结点
};

双链表的设计

双链表的结构：
双链表结构
关于双链表的插入操作：

// 假设在结点now的后面插入结点为p
p->next = now->next;
p->next->pre = p;
now->next = p;
p->pre = now;

插入结点
关于双链表的删除操作：

// 假设要删除的前一个结点为p
p->next = p->next->next;
p->next->pre = p;

删除结点
代码展示：

// 定义双链表的结点
struct ListNode {
	int val;
	ListNode* pre;
	ListNode* next;
	ListNode() : val(0), pre(nullptr), next(nullptr) {}
	ListNode(int val) : val(val), pre(nullptr), next(nullptr) {}
	ListNode(int val, ListNode* pre, ListNode* next) : val(val), pre(pre), next(next) {}
};

class MyLinkedList {
public:
	// 构造函数，初始化对象
    MyLinkedList() {
        virtualHead = new ListNode1(0);
        length = 0;
    }
    
    // 通过下标获取结点的值
    int get(int index) {
        if (index < 0 || index >= length)
            return -1;
        ListNode1* now = virtualHead;
        while (index) {
            now = now->next;
            index--;
        }
        return now->next->val;
    }
    
    // 在第一个元素之前插入一个结点
    void addAtHead(int val) {
        ListNode1* p = new ListNode1(val);
        if (!virtualHead->next) {
            virtualHead->next = p;
            p->pre = virtualHead;
        }
        else {
            p->next = virtualHead->next;
            virtualHead->next->pre = p;
            p->pre = virtualHead;
            virtualHead->next = p;
        }
        length++;
    }
    
    // 在链表末尾插入一个结点
    void addAtTail(int val) {
        ListNode1* p = new ListNode1(val);
        ListNode1* now = virtualHead;
        while (now->next) {
            now = now->next;
        }
        now->next = p;
        p->pre = now;
        length++;
    }
    
    // 在指定位置插入一个结点
    void addAtIndex(int index, int val) {
        if (index < 0 || index > length)
            return;
        if (index == 0) {
            addAtHead(val);
            return;
        }
        if (index == length) {
            addAtTail(val);
            return;
        }
        ListNode1* now = virtualHead;
        while (index) {
            now = now->next;
            index--;
        }
        ListNode1* p = new ListNode1(val);
        p->next = now->next;
        now->next->pre = p;
        now->next = p;
        p->pre = now;
        length++;
    }
    
    // 删除指定下标的结点
    void deleteAtIndex(int index) {
        if (index < 0 || index >= length)
            return;
        ListNode1* now = virtualHead;
        while (index) {
            now = now->next;
            index--;
        }
        ListNode1* p = now->next;
        if (!p->next) {
            now->next = nullptr;
            delete p;
        }
        else {
            p->next->pre = now;
            now->next = p->next;
            delete p;
        }
        length--;
    }
private:
    int length; // 链表的长度
    ListNode1* virtualHead; // 虚拟头结点
};