leetcode 算法刷题记录

2.addTwoNumbers

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0); //new一个ListNode
        //dummyHead是头结点，位置不变，用来返回的
        ListNode p = l1, q = l2, curr = dummyHead;
        //curr是操作节点，用来插入数据
        // System.out.println("p "+p+"\nl1 "+l1);
        //p ListNode@2503dbd3
        //l1 ListNode@2503dbd3
        //p 和 l1指向同一个对象
        // println 的执行，使runtime由1ms升至11ms，尽量少用
        
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;//carry是进位，留给下一个位使用
            curr.next = new ListNode(sum % 10);//创建新节点，加入链表
            curr = curr.next;//操作节点，指向最新的节点
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

ListNode
链表的操作对象是节点，链表在内存中的位置不连续。数组的操作对象是数组对象，而不是数组中的元素，在内存中的位置连续。这是两者最大的差别。在java中，链表的操作类是List，并没有像这里用到ListNode。这里使用ListNode是为了加深对链表的理解。

4. Median of Two Sorted Arrays
   Runtime: 21 ms, faster than 81.27% of Java online submissions for Median of Two Sorted Arrays.
   Memory Usage: 46.7 MB, less than 94.89% of Java online submissions for Median of Two Sorted Arrays.
   寻找中间位置的数字，或其平均值。用for循环来走，两个浮标各从两边往中间走。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] newNums = Arrays.copyOf(nums1, nums1.length+nums2.length);
        System.arraycopy(nums2, 0, newNums, nums1.length, nums2.length);
        Arrays.sort(newNums);
        System.out.println(Arrays.toString(newNums));
        int leftPoint = 0;
        int rightPoint = newNums.length-1;
        for(int i = 0;i<newNums.length;i++)
        {
            if(leftPoint==rightPoint-1 || leftPoint==rightPoint)
            {
               System.out.println("leftPoint:"+leftPoint+"rightPoint:"+rightPoint); System.out.println("leftPoint:"+newNums[leftPoint]+"rightPoint:"+newNums[rightPoint]);
                return (newNums[leftPoint] + newNums[rightPoint])/2.0;
                
            }
            leftPoint++;
            rightPoint--;
        }
        return 0;
    }