代码随想录刷题记录-java

链表

设计链表节点 和 单链表

//链表节点
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 MyLinkedList {
    int size;
    ListNode head;//虚拟头节点

    public MyLinkedList() {
        size = 0;
        head = new ListNode();
    }

    public int get(int index) {
        if(index < 0 || index >= size) return -1;
        ListNode cur = head;
        while(index-- != 0){
            cur = cur.next;
        }
        return cur.next.val;
    }

    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head.next; //这句一定要在后一句的前面
        head.next = newNode;
        size++;
    }

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

    public void addAtIndex(int index, int val) {
        if(index < 0 || index > size){
            return;
        }

        ListNode newNode = new ListNode(val);
        ListNode cur = head;
        while(index-- != 0){
            cur = cur.next;
        }
        newNode.next = cur.next;
        cur.next = newNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size) return;
        ListNode cur = head;
        while(index-- != 0){
            cur = cur.next;
        }
        cur.next = cur.next.next;
        size --;
    }
}

翻转链表

两种方法：

• 创建新的链表
• 更改next指向

//方法一
class Solution {
    //创建了一个新的链表
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null; //这里要指向null；不能是 new ListNode()
        while(head!=null){
            ListNode newNode = new ListNode(head.val);
            newNode.next = newHead;
            newHead = newNode;
            head = head.next;
        }
        return newHead;
    }
}

//方法二
class Solution {
    //更改next的指向
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while(cur != null){
            //由于在 更改next的指向 时会改变cur.next，因此要提前进行保存
            temp = cur.next;

            //更改next的指向
            cur.next = prev;
            prev = cur;

            //循环cur
            cur = temp;
        }
        return prev;
    }
}

二叉树

二叉树迭代遍历
二叉树的遍历总结（递归+迭代）

二叉树刷题技巧

1. 一定要判断所给的根节点是否为null ( 所给测试点为 root = [])

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    if(root == null){
        return res;
    }
}