20230421 | 203. 移除链表元素、707. 设计链表、206. 反转链表

1、203. 移除链表元素

方法1：不添加虚拟节点方式，但是要注意处理删除头部的数据
时间复杂度 O(n)
空间复杂度 O(1)

/*** 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) {//处理全部一样的while(head!=null && head.val == val){head = head.next;}//已经为null，提前退出if(head == null) return head; //前驱节点ListNode pre = head;//当前节点ListNode cur = head.next;while(cur!=null){if(cur.val == val){pre.next = cur.next; //前驱节点的指针指向当前节点的尾部}else{pre = cur; //前驱节点指向当前节点}cur = cur.next; //当前节点往后移动}return head;}
}

方法二：增加一个虚拟头节点，可以方便删除头部的数据，但主要返回时的位置是什么，构建头节点的时候要注意是：ListNode dump = new ListNode(-1,head); 或者是

public ListNode removeElements(ListNode head, int val) {//已经为null，提前退出if(head == null) return head; ListNode dump = new ListNode(-1,head);//前驱节点ListNode pre = dump;//当前节点ListNode cur = head;while(cur!=null){if(cur.val == val){pre.next = cur.next; //前驱节点的指针指向当前节点的尾部}else{pre = cur; //前驱节点指向当前节点}cur = cur.next; //当前节点往后移动}return dump.next;}

2、707. 设计链表

删除链表节点： 链表-删除节点

添加链表节点： 链表-添加节点

这道题目设计链表的五个接口：

获取链表第index个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第index个节点前面插入一个节点
删除链表的第index个节点

可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目

链表操作的两种方式：

直接使用原来的链表来进行操作。
设置一个虚拟头结点在进行操作。

class ListNode{int val; //值ListNode next;ListNode(){}ListNode(int val){this.val = val;}
}
class MyLinkedList {//size 存储链表元素的个数int size;//虚拟节点ListNode head;//初始化 MyLinkedList 对象。public MyLinkedList() {size =0;head = new ListNode(0);}//获取第index个节点的数值，注意index是从0开始的，第0个节点就是头节点public int get(int index) {//如果下标无效，则返回 -1 。if(index<0|| index>=size){return -1;}ListNode currNode = head; //当前//包含一个虚拟头节点，所以查找第index+1个节点for(int i=0;i<=index;i++){currNode = currNode.next;}//返回值return currNode.val;}// 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。// 等价于在第0个元素前添加public void addAtHead(int val) {addAtIndex(0,val); //借助按索引位置添加}//将一个值为 val 的节点追加到链表中作为链表的最后一个元素。//等价于在size+1的位置添加public void addAtTail(int val) {addAtIndex(size,val);}//将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。public void addAtIndex(int index, int val) {if(index>size) return;if(index<0) index = 0;size++;//链表长度+1//找到要插入节点的前驱ListNode pre = head;for(int i=0;i<index;i++){pre = pre.next;}ListNode toAdd = new ListNode(val); //创建节点toAdd.next = pre.next; //创建的节点指向插入的位置pre.next = toAdd; //指向当前节点}//如果下标有效，则删除链表中下标为 index 的节点。public void deleteAtIndex(int index) {if(index<0 || index>=size){return;}size--;if(index == 0) { //删除头节点的情况head = head.next;return;}//先找打前驱ListNode pre = head;for(int i=0;i<index;i++){pre = pre.next;}pre.next = pre.next.next; //指向改变，实现删除}
}/*** 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);*/

需要反复练习

3、206. 反转链表

/*** 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 reverseList(ListNode head) {if(head ==null || head.next ==null) return head;ListNode cur = head;//当前节点ListNode pre = null;//前驱节点while(cur!=null){ListNode temp = cur.next; //记录下一个节点的位置，防止找不到cur.next = pre; //第一次pre为空，实现链表的端口操作pre = cur; //前驱节点指向下一个cur = temp; //当前节点指向临时存储的节点(下一个节点)}return pre; //返回pre节点，是因为pre节点已经指向最后一个位置了,各自的指针已经转变，并且此时cur为null。我错误的以为是head，其实head只指向1一个值了}
}

注意： 返回pre节点，是因为pre节点已经指向最后一个位置了,各自的指针已经转变，并且此时cur为null。我错误的以为是head，其实head只指向1一个值了