算法训练营day03--203.移除链表元素+707.设计链表+206.反转链表

本文主要是介绍算法训练营day03--203.移除链表元素+707.设计链表+206.反转链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、203.移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/
文章讲解：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV18B4y1s7R9

1.1 初见思路

做过好几次了，用虚拟头节点来解决原头节点可能也需要删除的情况

1.2 具体实现

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {ListNode newHead = new ListNode();if(head==null){return head;}newHead.next=head;ListNode cur = head;ListNode pre = newHead;while(cur!=null){if(cur.val==val){pre.next=cur.next;}else{pre=cur;}cur=cur.next;}return newHead.next;}
}

1.3 重难点

二、 707.设计链表

题目链接：https://leetcode.cn/problems/design-linked-list/description/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

2.1 初见思路

需要考虑场景比较充分才能写好这道题

2.2 具体实现

//单链表
class ListNode {int val;ListNode next;ListNode(){}ListNode(int val) {this.val=val;}
}
class MyLinkedList {//size存储链表元素的个数int size;//虚拟头结点ListNode head;//初始化链表public MyLinkedList() {size = 0;head = new ListNode(0);}//获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点public int get(int index) {//如果index非法，返回-1if (index < 0 || index >= size) {return -1;}ListNode currentNode = head;//包含一个虚拟头节点，所以查找第 index+1 个节点for (int i = 0; i <= index; i++) {currentNode = currentNode.next;}return currentNode.val;}//在链表最前面插入一个节点，等价于在第0个元素前添加public void addAtHead(int val) {addAtIndex(0, val);}//在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加public void addAtTail(int val) {addAtIndex(size, val);}// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点// 如果 index 大于链表的长度，则返回空public void addAtIndex(int index, int val) {if (index > size) {return;}if (index < 0) {index = 0;}size++;//找到要插入节点的前驱ListNode pred = head;for (int i = 0; i < index; i++) {pred = pred.next;}ListNode toAdd = new ListNode(val);toAdd.next = pred.next;pred.next = toAdd;}//删除第index个节点public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}size--;if (index == 0) {head = head.next;return;}ListNode pred = head;for (int i = 0; i < index ; i++) {pred = pred.next;}pred.next = pred.next.next;}
}

2.3 重难点

三、206.反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/
文章讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1nB4y1i7eL

2.1 初见思路

虚拟头节点 + 双指针

2.2 具体实现

class Solution {public ListNode reverseList(ListNode head) {ListNode pHead = null;if(head==null || head.next==null){return head;}ListNode cur = head;while(cur!=null){ListNode next = cur.next;cur.next=pHead;pHead=cur;cur = next;}return pHead;}
}