回顾前面刷过的算法（4）

今天回顾一下下面三个算法，涉及到了动态规划、合并链表、位运算，好吧，让我们再次手敲一遍

//乘积最大子数组//思路: 维护三个变量，imax最大前缀乘积 imin最小前缀乘积  max最大连续乘积//由于元素有正负，imax和imin需要互换，所以需要单独维护一个max用于记录最大连续乘积public int maxProduct(int[] nums) {if (nums == null || nums.length == 0) {return -1;}if (nums.length == 1) {return nums[0];}int imax = 1, imin = 1, max = Integer.MIN_VALUE;for (int i = 0; i < nums.length; i++) {if (nums[i] < 0) {int temp = imax;imax = imin;imin = temp;}imax = Math.max(nums[i], imax * nums[i]);imin = Math.min(nums[i], imin * nums[i]);max = Math.max(max, imax);}return max;}//排序链表//思路: 先将链表分成多条长度为1（length）的子链表，然后合并两条长度为1的有序子链表，//接着把链表分为多条长度为2（length）的子链表，然后合并两条长度为2的有序子链表，//重复以上步骤，直到length大于等于链表的长度结束public ListNode sortList(ListNode head) {if (head == null) {return null;}int length = 0;ListNode curr = head;while (curr != null) {length++;curr = curr.next;}ListNode dummyHead = new ListNode(0, head);for (int subLength = 1; subLength < length; subLength = subLength * 2) {ListNode prev = dummyHead;curr = dummyHead.next;while (curr != null) {ListNode head1 = curr, head2;for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {curr = curr.next;}head2 = curr.next;curr.next = null;curr = head2;for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {curr = curr.next;}ListNode dailyListHead = null;if (curr != null) {dailyListHead = curr.next;curr.next = null;}prev.next = merged(head1, head2);while (prev.next != null) {prev = prev.next;}curr = dailyListHead;}}return dummyHead.next;}private ListNode merged(ListNode head1, ListNode head2) {ListNode dummyHead = new ListNode(0);ListNode temp = dummyHead, temp1 = head1, temp2 = head2;while (temp1 != null && temp2 != null) {if (temp1.val >= temp2.val) {temp.next = temp2;temp2 = temp2.next;} else {temp.next = temp1;temp1 = temp1.next;}temp = temp.next;}if (temp1 != null) {temp.next = temp1;} else if (temp2 != null) {temp.next = temp2;}return dummyHead.next;}//只出现一次的数字//思路: 利用异或运算进行求解，异或运算性质，0异或任何数都等于本身，任何数与本身异或都等于0public int singleNumber(int[] nums) {int single = 0;for (int i = 0; i < nums.length; i++) {single ^= nums[i];}return single;}