算法训练营Day3(链表)

语言

采用的Java语言，一些分析也是用于Java，请注意。

理论基础

对于链表我之前学的蛮多的，说基础的话，基本上就是说链表在内存上的不连续性

以及要和数组对比，数组知道下表之后，可以直接O（1）级别的查看，修改，而删除、新增不方便

而链表恰恰相反，修改、删除，移动指针就好了，而查看的话需要一个一个遍历

对于Java中的Arraylist和LinkedList那个性能高的时候，LinkedList发明者都说，链表虽然删除容易，但是要删除的前提也是要遍历找到哪个元素，因此在项目中还是基本上使用ArrayList

上面是我对链表的理解，

这里再说下对做题的理解，“一瓶酒、一包烟，一道链表刷一天”，链表题虽然不难，但是很考验编程能力，需要做的就是充分利用虚拟头节点和掌握几个链表的核心基础，如反转链表，移除链表等技巧，这些基本上要背会，因为这些是做某些链表题的基础。

另外，java的小伙伴还要学习一下jvm中的内存可达性算法，GC ROOT的原理，对于链表在内存中如何运行很有帮助，这个会了才方便理解链表题。

203.移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

不适用虚拟头节点

值得注意的是：while循环为什么多了一个cur!=null

当你使用一个指针（对象引用）的时候需要确保它是非空的这里如果用 cur 指向的是 head 无法保证 head 是非空的所以要对 cur 本身进行判断往后走如果用 pre 指向 dummy dummy是自己new的对象可以确保它是非空的所以用 pre.next 判断下一个节点

这也是为什么使用dummy节点的时候，while循环里可以省略掉cur！=null

有时候方便理解，我喜欢把cur写成pre。

public ListNode removeElements(ListNode head, int val) {
        while(head!=null && head.val==val){
            head=head.next;
        }

        //2
        //1 2 3 4
        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;
    }

使用虚拟头节点

public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1,head);
        //2
        //1 2 3 4
        ListNode pre = dummy;
        while (pre.next!=null){
            if(pre.next.val==val){
                pre.next = pre.next.next;
            }else {
                pre=pre.next;
            }
        }
        return dummy.next;
    }

707.设计链表

这道题就是考研链表的基本操作，需要注意几个点

1、头节点的巧用

2、更新、删除的时候需要找到n节点的上一个节点，也就是cur指针的next是要找的节点

3、判断是否符合要求的时候，可以用极限值来判断，比如第0个节点

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;
    }
}
public class MyLinkedList {
    /**
     * 链表个数
     */
    int size;
    /**
     * 虚拟头节点
     */
    ListNode dummy;
    public MyLinkedList() {
        size = 0;
        dummy = new ListNode(0);
    }

    public int get(int index) {
        //判断index是否有效
        if(index<0 || index>=size){
            return -1;
        }
        //注意这里是获取节点，因此不需要找到上一个节点，索引cur是dummy.next，
        //上一个节点的话，cur = dummy就可以了
        //因为=dummy的时候，cur正好是第0个节点的上一个
        ListNode cur = dummy.next;
        while(index-->0){
            cur = cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        ListNode newHead = new ListNode(val);
        newHead.next = dummy.next;
        dummy.next = newHead;
        size++;
    }

    public void addAtTail(int val) {
        ListNode cur = dummy;
        while(cur.next.next!=null){
            cur = cur.next;
        }
        ListNode newListNode = new ListNode(val);
        newListNode.next = null;
        cur.next = newListNode;
        size++;
    }

    public void addAtIndex(int index, int val) {
        ListNode cur = dummy;
        while(index-->0){
            cur = cur.next;
        }
        ListNode newListNode = new ListNode(val);
        newListNode.next = cur.next;
        cur.next = newListNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        ListNode cur = dummy;
        while(index-->0){
            cur= cur.next;
        }
        cur.next = cur.next.next;
        size--;
    }
}

206.反转链表

206. 反转链表 - 力扣（LeetCode）

双指针解法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

递归解法

class Solution {
     public ListNode reverseList(ListNode head) {
        return reverse(head,null);
    }
    public ListNode reverse(ListNode cur,ListNode pre){
        //递归终止条件
        if(cur==null){
            return pre;
        }
        ListNode temp = cur.next;
        cur.next = pre;
        return reverse(temp,cur);
    }
}