1. 链表题

  1. 一个长度为n的单向链表，用O(1) 空间复杂度来实现倒转输出，使用最低时间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        ListNode tmp = null;

        while(cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}
  1. 找出单链表的中间元素，要求用时最少
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode middleNode(ListNode head) {
        
        if(head == null) return null;
        
        ListNode fast = head;
        ListNode slow = head;

        while(fast!=null && fast.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
  1. 单链表中是否有环，写出代码
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast!= null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }
        return !(fast == null || fast.next == null);
    }
}
  1. 如果单链表中有环，请找到环的入口点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public ListNode findLoopNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) break;
        }
        
        if(fast == null || fast.next == null) return null;
        
        slow = head;
        
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return fast;
    }
}

2. 删除排序链表中的重复元素

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode tmp = new ListNode();
        tmp.next = head;
        ListNode pre =tmp;
        pre.next = head;
        ListNode cur = head;

        while(cur != null && cur.next != null) {
            if(pre.next.val != cur.next.val) {
                pre = pre.next;
                cur = cur.next;
            } else {
                while(cur!= null && cur.next != null && cur.next.val == pre.next.val) {
                    cur = cur.next;
                }
                pre.next = cur.next;
                cur = cur.next;
            }
        }
        
        return tmp.next;
    }
}

3. 简单排序

  1. 冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// TLE
class Solution {
    public int[] sortArray(int[] nums) {
        for(int i = 0;i < nums.length - 1;++i) {
            for(int j = i+1; j < nums.length;++j) {
                if(nums[i] > nums[j]) {
                    nums[i] = nums[i] + nums[j];
                    nums[j] = nums[i] - nums[j];
                    nums[i] = nums[i] - nums[j];
                }
            }
        }
        return nums;
    }
}
  1. 插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] sortArray(int[] nums) {
        for(int i = 1; i < nums.length; i++) {
            int j = i;
            while(j > 0 && nums[j] < nums[j - 1]) {
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
                j--;
            }
        }
        return nums;
    }
}

4. 快速排序代码

912. 排序数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] sortArray(int[] nums) {
        quick_sort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quick_sort(int nums[], int l, int r) {
        if(l >= r) return;

        int i = l -1, j = r + 1, x = nums[l+r >> 1];
        while(i < j) {
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);
            if(i<j) {
                nums[i] = nums[i] + nums[j];
                nums[j] = nums[i] - nums[j];
                nums[i] = nums[i] - nums[j];
            }
        }
        quick_sort(nums, l, j);
        quick_sort(nums, j + 1, r);
    }
}