【算法系列-链表】设计链表

【算法系列-链表】设计链表

1. 算法分析🛸

【题目链接】： LeetCode 707 设计链表

这是一道很经典的题，涵盖了链表的常见基本操作，包括：

• 获取第n个节点的值；
• 头部插入节点；
• 尾部插入节点；
• 在第n个节点前插入节点；
• 删除第n个节点的节点；

注：下述解题过程中使用到了虚拟头节点的方式进行操作，最开始都是从虚拟头节点开始遍历的，并且在单链表每次寻找节点都只找到目标节点的前一个节点，这样可以方便我们对目标节点进行操作

2. 解题过程🎬

2.1 初始化

2.1.1 思路分析🎯

最开始需要先定义好Node节点类，包括变量：val(节点值) 和 next(当前节点的下一个节点)，并设置对应的构造方法方便我们后续创建节点时能够直接赋值； 创建MyLinkedList的构造方法用来初始化 虚拟头节点head 和 链表长度 size

2.1.2 代码示例🌰

class Node {int val;Node next;public Node(){}public Node(int val) {this.val = val;}public Node(int val, Node next) {this.val = val;this.next = next;}
}class MyLinkedList {Node head;int size;public MyLinkedList() {this.head = new Node();size = 0;}...
}

之后编写对应的每个方法：

2.2 get(获取第n个节点的值)

2.2.1 思路分析🎯

当 index 大于 链表长度时，返回-1； 定义count用来表示当前cur所处位置，注，cur是从虚拟头节点开始遍历的，当count = 0时 cur 正在头节点上； 进入循环，当 cur != null && cur.next != null 时，进行判断： 当 count == index 时，表示当前 cur 的下一个节点就是目标节点 ，返回 cur.next.val 即可 当 count != index 时，cur 继续往下遍历，即 cur = cur.next; 判断结束后 无论结果 count 都要 + 1，重复上述过程直到返回结果

2.2.2 代码示例🌰

public int get(int index) {if (index > size) {return -1;}Node cur = head;int count = 0;while (cur != null && cur.next != null) {if (count++ == index) {return cur.next.val;}cur = cur.next;}return -1;     
}

2.3 addAtHead(头部插入节点)

2.3.1 思路分析🎯

构建 node 节点，并传入参数 val 与 head.next，使得 node节点的下一个节点 指向 当前头节点的下一个节点 之后让头节点的下一个节点指向 node节点，同时链表长度 + 1;

2.3.2 代码示例🌰

public void addAtHead(int val) {Node node = new Node(val, head.next);head.next = node;size++;
}

2.4 addAtTail(尾部插入节点)

2.4.1 思路分析🎯

构建 cur 节点并指向头节点head，后续通过cur进行遍历；构建node节点并赋值val； 进入循环：当 cur.next != null 时，cur继续往下遍历，直到 cur.next == null，表示当前cur已经是链表的最后一个节点了，最后让 cur.next 指向 node节点 即可，同时链表长度 + 1;

2.4.2 代码示例🌰

public void addAtTail(int val) {Node cur = head;Node node = new Node(val);while (cur.next != null) {cur = cur.next;}cur.next = node;size++;
}

2.5 addAtIndex(在第n个节点前插入节点)

2.5.1 思路分析🎯

当 index 大于 链表长度时，返回结果空； 定义count用来表示当前cur所处位置，注，cur是从虚拟头节点开始遍历的，当count = 0时 cur 正在头节点上； 进入循环，当 cur != null 时，进行判断： 当 count == index 时，表示当前 cur 的下一个位置就是目标插入位 ，构建node节点，并传入参数 val 与 cur.nex t，使得 node节点的下一个节点 指向 当前节点cur的下一个节点，之后让 cur的下一个节点指向当前 node节点，以此建立连接，最后 链表长度 + 1，返回结果空； 当 count != index 时，cur 继续往下遍历，即 cur = cur.next;

2.5.2 代码示例🌰

public void addAtIndex(int index, int val) {if (index > size) {return;}int count = 0;Node cur = head;while (cur != null) {if (count++ == index) {Node node = new Node(val, cur.next);cur.next = node;size++;return;}cur = cur.next;}
}

2.6 deleteAtIndex(删除第n个节点的节点)

2.6.1 思路分析🎯

当 index 大于 链表长度时，返回结果空； 定义count用来表示当前cur所处位置，注，cur是从虚拟头节点开始遍历的，当count = 0时 cur 正在头节点上； 进入循环，当 cur != null && cur.next != null 时，进行判断： 当 count == index 时，表示当前 cur 的下一个节点就是目标删除节点，则让 cur 的下一个节点指向 cur 的下一个节点的下一个节点，以此删除节点连接，最后链表长度 - 1，返回结果空; 当 count != index 时，cur 继续往下遍历，即 cur = cur.next;

2.6.2 代码示例🌰

public void deleteAtIndex(int index) {if (index > size) {return;}Node cur = head;int count = 0;while (cur != null && cur.next != null) {if (count++ == index) {cur.next = cur.next.next;size--;return;}cur = cur.next;}
}

3. 代码汇总🧮

class Node {int val;Node next;public Node(){}public Node(int val) {this.val = val;}public Node(int val, Node next) {this.val = val;this.next = next;}
}class MyLinkedList {Node head;int size;public MyLinkedList() {this.head = new Node();size = 0;}public int get(int index) {if (index > size) {return -1;}Node cur = head;int count = 0;while (cur != null && cur.next != null) {if (count++ == index) {return cur.next.val;}cur = cur.next;}return -1;}public void addAtHead(int val) {Node node = new Node(val, head.next);head.next = node;size++;}public void addAtTail(int val) {Node cur = head;Node node = new Node(val);while (cur.next != null) {cur = cur.next;}cur.next = node;size++;}public void addAtIndex(int index, int val) {if (index > size) {return;}int count = 0;Node cur = head;while (cur != null) {if (count++ == index) {Node node = new Node(val, cur.next);cur.next = node;size++;return;}cur = cur.next;}}public void deleteAtIndex(int index) {if (index > size) {return;}Node cur = head;int count = 0;while (cur != null && cur.next != null) {if (count++ == index) {cur.next = cur.next.next;size--;return;}cur = cur.next;}}
}

以上便是对设计链表类型题的介绍了！！后续还会继续分享其它算法系列内容，如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨