算法训练营第三天

前言

由于在火车上面，回家过年，所以晚了一天，赶紧补上。

感觉就第二题有点难度，其他的感觉还好

标题

203. 移除链表元素

/**
 * 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;
        }
        // 假如头节点为空直接返回，不然执行后面的代码会呈现空指向反常
        if (head == null) {
            return head;
        }
        // 记载前一个节点
        ListNode pre = head;
        // 要判别的节点
        ListNode temp = head.next;
        while(temp != null) {
            // 假如找到要删去的节点
            if (temp.val == val) {
                // 将前一节点指向要删去节点的后一节点
                pre.next = temp.next;
                // 判别的节点后移
                temp = temp.next;
                // 重新进入循环，持续判别
                continue;
            }
            // 假如没有找到
            // 要判别的节点后移一个
            temp = temp.next;
            // 记载前一个节点同时后移一个
            pre = pre.next;
        }
        return head;
    }
}

707. 设计链表

class MyLinkedList {
    class Node {
        Node prev, next;
        int val;
        Node (int _val) {
            val = _val;
        }
    }
    Node he = new Node(-1), ta = new Node(-1);
    int sz = 0;
    public MyLinkedList() {
        he.next = ta; ta.prev = he;
    }
    public int get(int index) {
        Node node = getNode(index);
        return node == null ? -1 : node.val;
    }
    public void addAtHead(int val) {
        Node node = new Node(val);        
        node.next = he.next; node.prev = he;
        he.next.prev = node; he.next = node;
        sz++;
    }
    public void addAtTail(int val) {
        Node node = new Node(val);
        node.prev = ta.prev; node.next = ta;
        ta.prev.next = node; ta.prev = node;
        sz++;
    }
    public void addAtIndex(int index, int val) {
        if (index > sz) return ;
        if (index <= 0) {
            addAtHead(val); 
        } else if (index == sz) {
            addAtTail(val);
        } else {
            Node node = new Node(val), cur = getNode(index);
            node.next = cur; node.prev = cur.prev;
            cur.prev.next = node; cur.prev = node;
            sz++;
        }
    }
    public void deleteAtIndex(int index) {
        Node cur = getNode(index);
        if (cur == null) return ;
        cur.next.prev = cur.prev;
        cur.prev.next = cur.next;
        sz--;
    }
    Node getNode(int index) {
        boolean isLeft = index < sz / 2;
        if (!isLeft) index = sz - index - 1;
        for (Node cur = isLeft ? he.next : ta.prev; cur != ta && cur != he; cur = isLeft ? cur.next : cur.prev) {
            if (index-- == 0) return cur;
        }
        return null;
    }
}

206. 回转链表

 /**
  * 思路：
  * 1. 递归，只考虑当前层逻辑即可
  * 时间：O(N)，空间：O(1)
  */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}