您现在的位置是：首页 >学无止境 >数据结构和算法-算法题网站首页学无止境

刷题进度 链表 5.反转链表

1.百度笔试：给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。 要求：空间复杂度O(1)，时间复杂度为O（n）

解题方法1(时间复杂度O(n^2),不符合要求):

/**
	 * 百度笔试：给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。 要求：空间复杂度O(1)，时间复杂度为O（n）
	 * 我的实现思路：
	 * 定义两个变量left和right，left初始值是0，right初始值是数组长度减1，从左往右遍历数组中元素时;
	 * 如果该元素是偶数，则从数组右边right位置开始遍历，遍历到第一个奇数时则将这两个元素值交换，
	 * 同时将right赋值为遍历到那个奇数的索引；
	 * 如果元素是奇数，则从数组左边left位置开始遍历，遍历到第一个偶数数时则将这两个元素值交换，
	 * 同时将left赋值为遍历到那个偶数的索引；
	 * Ps：不知道这样时间复杂度是不是O(n)，我感觉时间复杂度是O(n^2)
	 */
	public static void baiduSort(int[] testArray) {
		int left = 0;
		int right = testArray.length - 1;
		for (int i = 0; i < testArray.length; i++) {
			if (left < right) {
				//奇数
				if (testArray[i] % 2 == 1) {
					for (int j = left; j < i; j++) {
						//如果在i索引前面还有偶数，那么将偶数赋值为该奇数
						if (!(testArray[j] % 2 == 1)) {
							left = j;
							int temp = testArray[j];
							testArray[j] = testArray[i];
							testArray[i] = temp;
							break;
						}
					}
				} else {
					//偶数
					for (int j = right; j > i; j--) {
						//如果在i索引前面还有偶数，那么将偶数赋值为该奇数
						if (testArray[j] % 2 == 1) {
							right = j;
							int temp = testArray[j];
							testArray[j] = testArray[i];
							testArray[i] = temp;
							break;
						}
					}
				}
			}
		}
		System.out.println("排序后的数组：" + Arrays.toString(testArray));
	}

解题方法2(时间复杂度O(n)):

/**
	 * 百度笔试：给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。 要求：空间复杂度O(1)，时间复杂度为O（n）
	 */
private static void baiduSort2(int[] testArray) {
    int index = 0;
    int[] result = new int[testArray.length];

    //遍历奇数，将其添加到新的数组前面
    for (int i = 0; i < testArray.length; i++) {
        if (testArray[i] % 2 == 1) {
            result[index] = testArray[i];
            index++;
        }
    }
    //遍历偶数，将其添加到新数组奇数后面
    for (int i = 0; i < testArray.length; i++) {
        if (testArray[i] % 2 == 0) {
            result[index] = testArray[i];
            index++;
        }
    }
    System.out.println("排序后的数组：" + Arrays.toString(result));
}

这个地方还是对数组的理解不够,是可以创建出一个指定大小的空元素数组的int[] result = new int[testArray.length];然后就可以借助这个数组来存储我们筛选的奇数和偶数元素

2.给定一个二进制数据位数，输出所有2进制数所对应的所有的自然数，要求时间复杂度优先。喜马拉雅

https://ask.csdn.net/questions/382489?sort=votes_count

这道题的答案简直没看明白,我操了个DJ的,可能是里面包含的数学知识没有弄明白吧

3.删除有序数组中的重复项 小米

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

这道题要用到双指针才能解决,感觉有点像双链表中的指针那个意思

public int removeDuplicates(int[] nums) {
    //双指针解题方法
    int fast = 1, slow = 1;
    while(fast < nums.length){
        //判断当前结点和前一个结点元素值是否不等,不等则将后面一个结点的值赋值给前一个结点,同时前后结点的索引同时加1,fast++,slow++;如果前后两个结点的值相同,那么前面一个结点的值无需变化,只需要将后面一个结点指向下一个结点即可fast++
        if(nums[fast] != nums[fast - 1]){
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

4.如何在不使用递归的情况下逆转单链表head。小米/美团/快手

解题思路: 遍历整个单链表,将每个结点的next指针指向他的上一个结点,整个链表的指针指向就会反转,就达到了逆转单链表的目的.首先定义一个结点cur,用于记录头结点指向的下一个结点,然后将头结点head的next指针指向null(即逆转后的最后一个结点的next指针指向null),然后开始遍历cur链表,在遍历的过程中,将当前结点指向上一个结点.

方法1 (迭代),代码如下:

public ListNode reverseList(ListNode head) {
    //结点非空判断
    if(head == null){
        return null;
    }
    //定义一个结点,用于记录当前结点指针指向未反转前,指向的下一个结点
    ListNode cur = head.next;
    //反转后的指针,head结点反转后就是尾结点,他的指针指向null
    head.next = null;
    //遍历未反转的那个结点,将每个结点指向他的上一个结点
    while(cur != null){
        //记录指针未反转前的下一个结点
        ListNode next = cur.next;
        //将当前结点指向他的上一个结点,这就是反转操作
        cur.next = head;
        //反转后的结点指针后移
        head = cur;
        //未反转的结点指针后移
        cur = next;
    }
    //返回反转后的结点
    return head;
}

方法2 (递归),代码如下:

解题思路: 调用递归方法,然后将当前结点的下一个结点的next指针指向当前结点,将第一个结点的next指针指向null,否则链表会生成环.注意:链表长度大于等于2才能使用递归哦.

//递归法
public ListNode reverseList(ListNode head) {
    //结点非空判断
    if(head == null){
        return null;
    }
    //判断结点个数,有两个结点才能用递归
    if(head.next == null){
        return head;
    }
    //重新定义一个结点,用于记录head结点的一下结点
    ListNode cur = head.next;
    //反转后的head是列表的尾结点,他的next指针指向null
    head.next = null;
    return recursion(cur, head);
}


private ListNode recursion(ListNode node, ListNode prev){
    if(node.next == null){
        node.next = prev;
        return node;
    } else {
        ListNode head = recursion(node.next, node);
        node.next = prev;
        return head;
    }
}