阅文集团笔试

算法1

力扣328~

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

分析：

对于原始链表来说，头节点是奇数节点，头结点的下一个为偶数节点。令evenHead=head.next。则evenHead为偶数链表的头节点。

维护两个指针，odd和even分别指向奇数点和偶数点。初始值为odd=head，even = evenHead。

通过迭代的方式，将奇数节点和偶数节点分离成两个链表。每一步先更新奇数节点，后更新偶数节点。

更新奇数节点：odd.next = even.next; odd=odd.nex;

更新偶数节点：even = odd.next; even = even.next;

最后的结束条件是，even为null或者even.next为null。就是奇数链表的最后一个节点，最后将odd.next=evenHead。就是将奇数链表和偶数链表连接在一起。头节点仍然是head。

代码为：

public class Main {
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if(head==null) return head;
        ListNode evenHead = head.next;
        ListNode odd = head;
        ListNode even = evenHead;
        while (even!=null && even.next!=null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

算法2

力扣88~

合并两个有序链表。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

方法一：

直接将nums2中的元素加入到num1中，再对num1排序就可。

代码为：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

方法二：

借助一个数组，通过双指针，存放num1和num2比较结果最小的一个

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0;
        int p2 = 0;
        int res[] = new int[m+n];
        int index = 0;
        while (p1<m && p2<n){
            if (nums1[p1]<nums2[p2]){
                res[index++] = nums1[p1];
                p1++;
            }else {
                res[index++] = nums2[p2];
                p2++;
            }
        }
        while (p1<m) res[index++] = nums1[p1++];
        while (p2<n) res[index++] = nums2[p2++];
        for (int i = 0;i<m+n;i++){
            nums1[i] = res[i];
        }
    }
}

方法三：

方法二中，之所以要使用临时变量，是因为如果直接合并到数组nums 1中，nums 1中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖nums 1中的元素呢？观察可知，nums 1的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进nums 1 的最后面。

1. 思路的重点一个是从后往前确定两组中该用哪个数字

2. 另一个是结束条件以第二个数组全都插入进去为止

   直接在nums1数组上进行修改。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = nums1.length;
        
        while (n > 0) {
            if (m > 0 && nums1[m - 1] > nums2[n - 1]) {
                nums1[i - 1] = nums1[m - 1];
                i--;
                m--;
            }else {
                nums1[i - 1] = nums2[n - 1];
                i--;
                n--;
            }
        }
    }
}