为了转行程序员而努力的第二十七天-链表，虚方法，Deque

为了转行程序员而努力的第二十七天-链表，虚方法，Deque

今天又做噩梦了，梦里有一种深深的无力感，醒了之后觉得自己很没用，似乎起床之后情绪低落是比较普遍的现象。快春节了，看了看回家的票，往返的票加起来，够一个月的生活费了，再看看自己的工资，都不舍得回家，觉得就这么几天，一下子花去这么多，又觉得挣钱太少，没脸回去，但又始终下不了干脆不回家过年的决心，也没找到工资更高的工作，甚至简历都没准备好，就这么耗着，准备期太漫长太难熬了。

近乎麻木地看题，刷题，看题解，不知不觉也一道道刷下来了，练习的过程是枯燥而痛苦的，然而正是在这些看似无用的反复重复中，才能渐渐熟练起来，没有人可以不努力就掌握一门技术，就算是有天赋，没有踏踏实实的努力练习，没有在某一方面花很长的时间钻研，也根本发挥不出来，只靠耍小聪明是行不通的，这样的过程也是一种内心的修行了。

今日进度：
1.坚持刷题，今天完成了链表的大部分练习题，还剩下两道留给明天了
2.坚持录小王子，昨天其实没有时间了，今天不要落下
3.坚持锻炼，十几分钟强度一般的训练很适合做日常的训练，肩颈运动也很适合久坐不动的人
4.坚持早睡
5.坚持记录进度
6.晚饭少吃，这个算是部分做到了吧

学习笔记：
1.Deque是Queue子接口，是双端队列。可以同时从两端（队列头部和尾部）添加、删除元素。所以可以用来实现栈的数据结构。有两个实现类（ArrayDeque和linkedList）
void push(E e)：栈方法，push元素进入该双端队列表示栈的栈顶，等价于addFist()方法。
E pop()：栈方法，pop出该双端队列表示栈的栈顶元素，等价于removeFirst()方法。
2.Salary继承了Employee类，并且重写了同名方法mailCheck（），在编译的时候，编译器使用Employee类中的mailCheck()方法验证该语句， 但是在运行的时候，Java虚拟机(JVM)调用的是Salary类中的mailCheck()方法。该行为被称为虚拟方法调用，该方法被称为虚拟方法。
3.203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

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

解题思路：从头节点开始遍历链表，如果当前的值等于需要删除的值，将前一个节点的next指针指向当前的next节点，令当前节点等于下一个节点。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dn = new ListNode(0);
        ListNode pre = dn;
        dn.next = head;
        while(head != null){
            if(head.val == val){
                pre.next = head.next;
                head = head.next;
            }
            else{
                pre = head;
                head = head.next;
            }
        }
        return dn.next;
    }
}

4.328. 奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

解题思路：使用两个链表，分别存储奇数节点和偶数节点，再将奇数节点的末尾指向偶数节点的开头，使用两个指针，一个指向head，是奇数链表的开头，一个指向head.next，是偶数链表的开头

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode odd = head;
        ListNode even = head.next;
        ListNode oddH = odd;
        ListNode evenH = even;
        while(even!=null && even.next!=null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenH;
        if(even != null){
            even.next = null;
        }
        
        return oddH;
    }
}

5.2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

解题思路：由于数字按照逆序的方式存储，将两个链表每一位对应的数字加起来，如果大于10，就在下一位加1，或者新增一个节点

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode n = new ListNode(0);
        ListNode nh = n;
        int next = 0;
        int l1t = 0, l2t = 0;
        while(l1!=null || l2!=null){
            if(l1 == null){
                l1t = 0;
                l2t = l2.val;
            }
            else if(l2 == null){
                l2t = 0;
                l1t = l1.val;
            }
            else{
                l1t = l1.val;
                l2t = l2.val;
                }
            int s = l1t+l2t+next;
            next = 0;
            if(s >= 10){
                s = s-10;
                next = 1;
            }
            n.next = new ListNode(s);
             n = n.next;
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }
        if(next == 1){
            n.next = new ListNode(1);
            n = n.next;
        }
        return nh.next;
    }
}

6.445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

解题思路：使用两个栈来存储链表中的每个节点，这样从栈中d出的就是逆序的数字，将两个栈中的数字加起来，如果大于10，进位为1，或者新增一个节点，最后将新的节点从后往前连接起来，返回头节点即可

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque s1 = new linkedList();
        Deque s2 = new linkedList();
        ListNode ans = null;
        while(l1!=null){
            s1.push(l1.val);
            l1=l1.next;
        }
        while(l2!=null){
            s2.push(l2.val);
            l2=l2.next;
        }
        int carry = 0;
        while(!s1.isEmpty() || !s2.isEmpty() || carry!=0){
            int l1t,l2t = 0;
            l1t = s1.isEmpty() ? 0:s1.pop();
            l2t = s2.isEmpty() ? 0:s2.pop();
            int s = l1t+l2t+carry;
            int tc = s % 10;
            carry = s / 10;
            
            ListNode tmp = new ListNode(tc);
            tmp.next = ans;
            ans = tmp;
        }
        return ans;
    }
}

不知不觉又到这个点了，好像一到晚上就有点控制不住自己在零碎的事情或者发呆上花时间，明日继续更新。