算法学习day03：移除链表元素，设计链表，反转链表（Java）

前言：链表是一种存储数据的方法，由一个个节点组成，每一个节点包括自身的值和下一个节点的地址（单向链表），最后一个节点指向的地址为null
Java中没有单向链表，需要自己手搓一个出来
以下代码为单向链表ListNode

public class ListNode {
    int val;//自身的值
    ListNode next;// 下一个节点

	//以下为构造器
    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

移除链表元素

题意：删除链表中等于给定值 target 的所有节点。

示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2： 输入：head = [], val = 1 输出：[]

示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]

根据链表的特性，不难看出，如果想要删除链表元素的话，只需要把 目标节点的前一个节点的地址 指向 目标节点的下一个节点 即可完成。删除理应很简单，但要考虑如果删除的链表是头节点（即第一个节点）的特殊情况
代码如下：

public ListNode delete01(ListNode head, int target){
    while(head != null && head.val == target){//如果删除的是头节点
        head = head.next;
    }
    if(head == null){//如果头节点为空，说明链表也是空的，返回null
        return head;
    }
    //以下情况为：要删除的目标不是头节点，且链表不为空
    ListNode current = head;
    if(current.next.val == target){//如果current的下一个节点是目标节点
        current.next = current.next.next;//把current节点指向current的下下个节点
    }else {//current没找到目标，向下走一位
        current = current.next;
    }
    return head;
}

配合注释，大概说明的差不多了，这里有一点需要注意：删除头节点的判断要用while，不能用if，以例题3举例，如果用的是if，那么头节点已经被删除，变成
[7(被忽略),7(head),7,7]
然后if语句执行完，继续往下走，删除到最后会变成
[7(被忽略),7(head),7(被删除),7(被删除)]

这样的思路虽然比较清晰，但代码还是相对冗杂的（因为有对头节点的特殊处理）
那么，有没有一种方法可以“一视同仁”地处理所有节点呢？自然是有的，我们在链表头部放一个虚拟的head节点（以下为DummyHead），那么所有原来的节点都不是头节点了，可以统一处理
具体代码如下：

public ListNode delete02(ListNode head, int target){
    ListNode DummyHead = new ListNode();
    DummyHead.next = head;//让DummyHead指向原来的“头节点”
    ListNode current = DummyHead;
    //以下代码和上面的代码一致
    if(current.next.val == target){
        current.next = current.next.next;
    }else {
        current = current.next;
    }
    return DummyHead.next;
}

203.力扣相关题目
代码随想录：移除链表元素

设计链表

之前手搓的链表初具雏形，现在对其进行一些设计，增加几个方法：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。

• addAtHead(target)：在链表的第一个元素之前添加一个值为 target的节点。插入后，新节点将成为链表的第一个节点。

• addAtTail(target)：将值为 target 的节点追加到链表的最后一个元素。

• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

没有太难的，以下为代码：（其实没有亲自测试过）

class MyLinkedList{
   int length;//链表的长度
   ListNode DummyHead;//虚拟头节点
   public MyLinkedList(){//调用无参构造器时，初始化长度为0，创造一个链表
       length = 0;//虽然链表实际长度为1，但这个是虚拟头节点，所以写长度为0
       DummyHead = new ListNode(0);//值为0的虚拟头节点
   }


//1.获取链表第index个值的节点，如果索引无效则返回-1
public int get(int index){
   ListNode current = DummyHead.next;//current指向真正的头节点
   if(index > length || index < 0){//数据非法的情况
       return -1;
   }
   for (int i = 0; i <index ; i++) {
       current = current.next;
   }
   return current.val;
}

//2.在链表的第一个元素之前添加一个值为 target 的节点。插入后，新节点将成为链表的第一个节点。
public void addAtHead(int target){
   ListNode current = DummyHead.next;
   ListNode targetNode = new ListNode(target, current);
   DummyHead.next = targetNode;
   length++;
}

//3.将值为 target 的节点追加到链表的最后一个元素。
public void addAtTail(int target){
   ListNode current = DummyHead.next;
   while (current.next != null){
       current = current.next;
   }
   ListNode targetNode = new ListNode(target,null);
   current.next = targetNode;
   length++;
}

// 4.addAtIndex(index,target)
// 在链表中的第 index 个节点之前添加值为 target 的节点。
// 如果 index 等于链表的长度，则该节点将附加到链表的末尾。
// 如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
public void addAtIndex(int index, int target){
   if(index > length){
       return;
   }else if(index < 0){
       this.addAtHead(target);
   }
   ListNode targetNode = new ListNode(target);
   ListNode current = DummyHead.next;
   for (int i = 0; i < index-1; i++) {
       current = current.next;
   }//此时current已经到达目标节点的前一位
   targetNode.next = current.next;
   current.next = targetNode;
   length++;
}

//5.deleteAtIndex(index)：
//如果索引 index 有效，则删除链表中的第 index 个节点。
public void deleteAtIndex(int index){
   if(index > length || index < 0){
       System.out.println("illegal data！");
       return;
   }
   ListNode current = DummyHead.next;
   for (int i = 0; i < index-1; i++) {
       current = current.next;
   }//此时current为要删除的节点的前一个节点
   current.next = current.next.next;
   length--;
}

上面的代码和原本的ListNode放在一起，就实现了对单向链表的简单增删改查

没有太多的技术性， 只是每个方法都需要思考current在哪里，故不做太多解释。作者太懒了

707.力扣相关题目
代码随想录：设计链表

反转链表

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
可以设计一个新的链表 最好不要设计一个新的链表，对内存空间太浪费了，我们尝试在原链表上动刀
我们需要把链表的next进行更改，往前指就可以了，这里用双指针很方便

思路：使用一个cur指针，一个pre指针，一前一后，让cur向前指向pre，对每个数据进行操作即可
原链表进行反转的话，本来5后面为null，反转后是1后面为null
NULL->1->2->3->4->5->NULL（这里作者实在不知道怎么描述了……）

让pre指向前面的NULL，cur指向1，开始进行反转，但进行完第一步后会发现变成了这样：
NULL<-1（断层）2->3->4->5->NULL

因此，为了保留原来的链表完整，我们应该再引入一个临时指针temp，帮忙定位到断层后的链表
进行完第一步后，让pre（左NULL）跑到cur（1）的位置，再让cur跑到temp（2）的位置，继续反转
注意：这里的顺序很重要，如果让cur先跑到了temp，pre就无法跑到cur原来的位置了
最后思考一下，什么时候完成任务（让循环终止），当cur走到右边的NULL的时候，所有的数据都完成了反转。

代码如下：

public static ListNode reverse01(ListNode head){
    ListNode cur = head;
    ListNode pre = null;
    ListNode temp;
    while (cur != null){
        temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

注意：完成最后一步后，cur指向null，pre指向现在的head，所以return的值是pre

也可以用递归法解决问题，核心思想和双指针（还是三指针？）法一样

代码如下：

public static ListNode reverse02(ListNode head){
    return reverseListNode(head, null);
}
public static ListNode reverseListNode(ListNode cur, ListNode pre){
    ListNode temp;
    if(cur == null){
        return pre;
    }
    temp= cur.next;
    cur.next = pre;
    return reverseListNode(temp, cur);
}

做一些解释

• 直接调用reverse02即可，return的reverseListNode(head, null)对应指针法的cur = head, pre = null

• 递归里的return reverseListNode(temp, cur)对应指针法的cur = temp, pre = cur

206.力扣相关题目
代码随想录：反转链表
今日学习时长：1h+50min+50min