203.移除链表元素
题目链接：力扣
思路
一般方法：对于一般删除链表元素的方法而言，我们需要分情况进行处理，分为被删除节点是头节点和被删除节点不是头节点的情况。如果是头节点，就将下一个节点赋值给头节点；如果非头节点，就进行常规删除
虚拟头节点：其实就是给头节点前面放一个虚拟节点，这样如果删除头节点的话就可以使用常规删除方法进行删除了
移除链表元素
一般方法
第一步：判断删除头节点的情况（注意：这里使用的是while关键字，这里是一个连续排查的过程，有前几个节点都是目标值的情况）
第二步：创建指针指向头节点（这里是头节点已经被删除干净的头节点）
第三步：进行判断，被删除的这个节点会被绕过，所以要使用cur.next 进行判断：如果不是，指针前移；如果是，越过删除
/** * 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; } //创建一个指针 ListNode cur = head; while ( cur != null && cur.next != null ) { if ( cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; } }
虚拟头节点
第一步：创建虚拟节点
第二步：按照上个方法的第二步和第三步进行操作
第三步：注意返回的是虚拟节点的next 才是真正的head
class Solution { public ListNode removeElements(ListNode head, int val) { //创建虚拟头节点 ListNode dummy = new ListNode(0); dummy.next = head; ListNode cur = dummy; while ( cur != null && cur.next != null ) { if ( cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } return dummy.next; } }
707.设计链表
题目链接：力扣
思路
这个题目包含了对链表元素的增删改查，其中get(int index)是查；addAtHead(int val)、addAtTail(int val)、addAtIndex(int index, int val)是增；deleteAtIndex(int index)是删
设计链表
单向链表实现：
第一步：定义单向链表的节点
第二步：定义链表的属性和链表
第三步：get(int index)
1、对非法下标进行判断
2、创建指针来取值
3、循环下标的次数，将指针指向要取的节点
4、返回获取的值
第四步：addAtIndex(int index, int val) 这个方法实现了，其他两个添加节点的方法也就实现了
1、对非法下标进行判断
2、创建要添加的节点、，创建临时指针
3、循环到指定的下标下，添加节点
4、链表长度增加
第五步：deleteAtIndex(int index)
这里和203 移除链表元素差不多
// 定义单向链表节点 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个节点的数值，下标从0开始 public int get(int index) { // index小于0或者大于size-1的情况都是无效的索引 if ( index < 0 || index > size - 1 ) { return -1; } // 创建一个指针来取值 ListNode cur = head; // 这里cur指向的是虚拟头节点 // 这样当索引为0的时候，下面的循环执行一次，cur刚好指向真正的头节点 for (int i = 0; i <= index ;i++) { cur = cur.next; } return cur.val; } public void addAtHead(int val) { addAtIndex(0,val); } public void addAtTail(int val) { addAtIndex(size,val); } public void addAtIndex(int index, int val) { // 对非法下标进行判断 if (index > size) { return; } if (index < 0) { index = 0; } // 创建要添加的指针 ListNode add = new ListNode(val); // 对链表元素进行添加 ListNode tmp = head; // 将tmp指针移动到 for (int i = 0 ; i < index ; i++) { tmp = tmp.next; } add.next = tmp.next; tmp.next = add; // 对链表长度进行增加 size++; } public void deleteAtIndex(int index) { // 对非法下标进行判断 if (index < 0 || index > size - 1) { return; } // 如果是头节点，将头节点向前移一位 if (index == 0) { head = head.next; return; } ListNode cur = head; for (int i = 0 ; i < index ; i++) { cur = cur.next; } cur.next = cur.next.next; // 链表长度减一 size--; } }
双向链表实现：
class ListNode{ int val; ListNode next,prev; ListNode () {} ListNode (int val) { this.val = val; } } class MyLinkedList { // 记录链表中的元素 int size; // 记录链表的虚拟头节点和尾节点 ListNode head; ListNode tail; public MyLinkedList() { // 初始化操作 this.size = 0; this.head = new ListNode(0); this.tail = new ListNode(0); head.next = tail; tail.prev = head; } public int get(int index) { // 判断下标的合法性 if (index < 0 || index >= size) { return -1; } // 创建一个指针 ListNode cur = this.head; // 判断哪一边的遍历时间更短 if (index >= size / 2) { // 从tail开始遍历 cur = tail; for (int i = 0 ; i < size - index ; i++) { cur = cur.prev; } } else { for (int i = 0 ; i <= index ; i++) { cur = cur.next; } } return cur.val; } public void addAtHead(int val) { //等价于在第0个元素前添加 addAtIndex(0,val); } public void addAtTail(int val) { //等价于在最后一个元素(null)前添加 addAtIndex(size,val); } public void addAtIndex(int index, int val) { // 判断下标的合法性 if(index>size){ return; } //index小于0 if(index<0){ index = 0; } ListNode pre = this.head; for(int i=0; i<index; i++){ pre = pre.next; } //新建结点 ListNode newNode = new ListNode(val); newNode.next = pre.next; pre.next.prev = newNode; newNode.prev = pre; pre.next = newNode; // 长度增加 size++; } public void deleteAtIndex(int index) { // 判断下标的合法性 if (index < 0 || index >= size) { return; } // 删除操作 ListNode pre = this.head; for (int i = 0 ; i < index ; i++) { pre = pre.next; } pre.next.next.prev = pre; pre.next = pre.next.next; // 长度减少 size--; } }
206.反转链表
题目链接：力扣
思路
双指针：其实可以称为三指针了，cur负责指向pre，tmp负责临时保存
递归法：是双指针的优化
反转链表
双指针法
第一步：定义双指针
cur指向头节点，pre指向null（反转时后节点指向前节点的方向）
第二步：在cur指向null的时候循环结束
要创建一个临时节点保存cur反转后后面的节点，防止丢失
注意：在反转成功后，在移动指针的时候，要先移动pre，再移动cur
/** * 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) { ListNode pre = null; ListNode cur = head; while (cur != null) { // 利用临时指针保存cur后的下一个节点，防止找不到 ListNode tmp = cur.next; cur.next = pre; // 注意这里先移动pre 再移动cur pre = cur; cur = tmp; } return pre; } }
递归法
class Solution { public ListNode reverseList(ListNode head) { return reverse(null , head); } private ListNode reverse(ListNode prev , ListNode cur) { if (cur == null) { return prev; } ListNode tmp = null; tmp = cur.next; // 保存下一个节点 cur.next = prev; // 反转指针 return reverse(cur,tmp); } }
