数据结构与算法刷题——数据结构- 数组、链表(1.3)

发表于 分类于 ， 阅读时长 ≈ 8 分钟

一 概述

1
2
3
4
5
6
1. 两数之和
2. 三数之和 / 四数之和
3. 合并两个有序链表
4. 环形链表（快慢指针）
5. K 个一组翻转链表
6. 链表排序（归并）

二 解答(仅供参考)

2.1 两数之和

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
27
28
29
30
31
一、题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的下标。

二、Java 实现（哈希表解法，时间复杂度 O(n)）：

import java.util.HashMap;
public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>(); // 记录数值及其索引
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i]; // 目标值 - 当前值 = 所需的另一个值
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i); // 当前值入表
        }
        return new int[]{-1, -1}; // 没找到
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("结果下标: " + result[0] + ", " + result[1]); // 输出: 0, 1
    }
}

三、思路简述：
3.1 用哈希表存储访问过的数字及其索引。
3.2 每访问一个数字，判断 target - 当前数字 是否在表中。
3.3 若存在，即为答案。

2.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
一、三数之和（3Sum）
找出数组中所有和为 0 的不重复三元组。

Java 实现（排序 + 双指针）

import java.util.*;
public class ThreeSum {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // 先排序
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重

            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 去重
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    left++; right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum(nums));
    }
}

二、四数之和（4Sum）
找出数组中所有和为 target 的不重复四元组。

Java 实现（排序 + 双指针）

import java.util.*;
public class FourSum {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重

            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 去重

                int left = j + 1, right = n - 1;

                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                        // 去重
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;

                        left++; right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        System.out.println(fourSum(nums, target));
    }
}

三、总结
算法	    思路关键	     时间复杂度（平均）
3Sum	排序 + 双指针	     O(n²)
4Sum	双层循环 + 双指针	    O(n³)

2.3 合并两个有序链表

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
一、题目描述
给定两个升序的链表 l1 和 l2，将它们合并成一个新的升序链表并返回。

二、Java 实现（递归 + 非递归两种方式）
2.1 方式一：递归写法（简洁优雅 ✅）

public class MergeTwoSortedLists {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;       // 如果l1为空，返回l2
        if (l2 == null) return l1;       // 如果l2为空，返回l1

        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2); // 递归合并
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    // 辅助方法：打印链表
    public static void print(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    // 示例测试
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        ListNode merged = mergeTwoLists(l1, l2);
        print(merged); // 输出: 1 2 3 4 5 6
    }
}
2.2 方式二：非递归写法（迭代方式 ✅）
public static ListNode mergeTwoListsIterative(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0); // 虚拟头结点
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    // 连接剩余部分
    current.next = (l1 != null) ? l1 : l2;

    return dummy.next;
}

2.4 环形链表（快慢指针）

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
当然！这题就是判断链表中是否存在环，快慢指针法是最常见也最高效的解法。

一、环形链表：快慢指针法（Floyd 判圈算法）
1.1 思路：
-用两个指针：
 -slow 每次走一步；
 -fast 每次走两步；
-如果链表里有环，fast 和 slow 最终一定会在环中相遇；
-如果没有环，fast 会先走到 null。

1.1 Java 实现：

public class LinkedListCycle {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            if (slow == fast) return true; // 相遇，说明有环
            slow = slow.next;
            fast = fast.next.next;
        }

        return false; // fast 走到 null，说明无环
    }

    // 简单测试
    public static void main(String[] args) {
        ListNode a = new ListNode(3);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(0);
        ListNode d = new ListNode(-4);

        a.next = b;
        b.next = c;
        c.next = d;
        d.next = b; // 形成环

        System.out.println(hasCycle(a)); // 输出 true
    }
}

二、拓展：
如果你想要：
-返回环的起点节点 ——> 可以再加一步找入口；
-删除环 ——>  需要先找出环入口再处理；
-检测环长度 ——> 可以在相遇时多走一圈计数。

2.5 K 个一组翻转链表

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
一、题目描述：K 个一组翻转链表（Leetcode 25）
给你一个链表，每 K 个一组进行翻转，最后不足 K 个的部分保持原样。

二、Java 实现（递归写法）

public class ReverseKGroup {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode node = head;
        for (int i = 0; i < k; i++) {
            if (node == null) return head; // 不足 k 个，不翻转
            node = node.next;
        }

        // 翻转前 k 个节点
        ListNode newHead = reverse(head, k);

        // 递归处理剩下的部分
        head.next = reverseKGroup(node, k);

        return newHead;
    }

    // 翻转 k 个节点
    private static ListNode reverse(ListNode head, int k) {
        ListNode prev = null, cur = head;
        while (k-- > 0) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev; // 新头节点
    }

    // 打印链表
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    // 示例测试
    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        a.next = new ListNode(2);
        a.next.next = new ListNode(3);
        a.next.next.next = new ListNode(4);
        a.next.next.next.next = new ListNode(5);

        ListNode result = reverseKGroup(a, 3);
        printList(result); // 输出: 3 2 1 4 5
    }
}

三、思路总结：
-每次找 k 个节点；
-如果不满 k 个，直接返回原链表；
-翻转前 k 个节点，然后递归处理剩下部分；
-把当前翻转的尾节点（原 head）连接递归结果。

2.6 链表排序（归并）

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
链表排序经典解法是 —— 归并排序，因为它稳定且适合链表结构（不像快排那样依赖随机访问）。

一、题目描述：链表排序（Sort List）
给你一个链表，对其进行升序排序。

二、Java 实现：归并排序（自顶向下，分治 + 递归）

public class SortLinkedList {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        // 1. 快慢指针找中点
        ListNode slow = head, fast = head.next; // fast 提前一格保证分成两段
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. 分成左右两部分
        ListNode mid = slow.next;
        slow.next = null;

        // 3. 分别排序（递归）
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        // 4. 合并两个有序链表
        return merge(left, right);
    }

    // 合并两个有序链表
    private static ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    // 打印链表
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    // 示例测试
    public static void main(String[] args) {
        ListNode a = new ListNode(4);
        a.next = new ListNode(2);
        a.next.next = new ListNode(1);
        a.next.next.next = new ListNode(3);

        ListNode result = sortList(a);
        printList(result); // 输出: 1 2 3 4
    }
}
三、核心要点：

操作	          技术手段
找中间节点	    快慢指针
拆分链表	     断开 next
合并有序链表	    双指针/模拟合并
排序	          递归归并


时间复杂度为 O(n log n)，空间复杂度为递归栈的 O(log n)。