算法

【新手004】链表及简单题

Posted by Hilda on September 6, 2025

image-20250902234419825

单链表：值，一条next指针

双链表：值，一条last指针，一条next指针

玩出无尽的花样！！！

1.单链表的反转

1.1单链表反转

力扣：https://leetcode.cn/problems/reverse-linked-list/description/

牛客：https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = null, cur = head, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

力扣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre= cur;
            cur = next;
        }
        return pre;        
    }
}

1.2指定区间反转单链表

力扣：92 题 https://leetcode.cn/problems/reverse-linked-list-ii/description/

牛客：https://www.nowcoder.com/practice/f11155006f154419b0bef6de8918aea2?tab=note （ACM风格）

力扣：

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 需要另外考虑left == 1的情况
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // n == 1,只有一个节点,另外1 <= left <= right <= n   left == right时，不需要反转
        if (head.next == null || left == right) return head;
        // 遍历到left
        int i = 1;
        ListNode cur = head, pre = null;
        while (i < left) {
            pre = cur;
            cur = cur.next;
            i++;
        }
        ListNode p1tail = pre; // 第一部分的尾巴
        pre = cur;
        cur = cur.next;
        // 开始反转
        ListNode next = null, p2tail = null;
        while (i < right) {
            if (i == left) p2tail = pre;
            i++;
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        if (p1tail == null) {
            head = pre;
        } else {
            p1tail.next = pre;
        }

        p2tail.next = cur;
        return head;
    }
}

牛客：https://www.nowcoder.com/practice/f11155006f154419b0bef6de8918aea2?tab=note (ACM风格)

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

import java.util.Scanner;

import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int)in.nval;// 链表长度
            in.nextToken();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++ ) {
                arr[i] = (int)in.nval;
                in.nextToken();
            }
            ListNode head =  arrToListNode(arr, n);
            int left = (int)in.nval;
            in.nextToken();
            int right = (int)in.nval;
            in.nextToken();
            ListNode ans = reverseBetween(head, left, right);
            while (ans != null) {
                out.print(ans.val + " ");
                ans = ans.next;
            }
        }
        out.flush();
        br.close();
        out.close();
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || left == right) return head;
        ListNode pre = null, cur = head, next = null;
        ListNode p1Tail = null, p2Tail = null;
        int i = 1;
        while (i < left) {
            pre = cur;
            cur = cur.next;
            i++;
        }
        p1Tail = pre;
        pre = cur;
        cur = cur.next;
        while (i < right) {
            if (i==left) p2Tail = pre;
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
            i++;
        }
        if (p1Tail == null) {
            head = pre;
        }else {
            p1Tail.next = pre;
        }
        p2Tail.next = cur;
        return head;
    }
    public static ListNode arrToListNode(int[] arr, int n) {
        if (n == 0) return null;
        ListNode head = new ListNode(arr[0]);
        ListNode cur = head;
        for (int i = 1; i < n; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }

        return head;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {

    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode (int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

1.3 K个一组反转

力扣上有一道题是两两反转，对应的是这题的特殊情况k=2。

K个一组反转 – 力扣：https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

K个一组反转 – 牛客（填函数风格）：https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?fromPut=????pc????_???????_6243324481684200097423

解法：

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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode start = head, end = null;
        end = getKGroupEnd(start, k);
        if (end == null) { // 第一组都凑不齐
            return head;
        }
        // 第一组凑齐了
        head = end;
        reverse(start, end);
        ListNode lastEnd = start;
        while (lastEnd.next != null) {
            start = lastEnd.next;
            end = getKGroupEnd(start, k);
            if (end == null) {
                return head;
            }
            reverse(start, end);
            lastEnd.next = end;
            lastEnd = start;
        }
        return head;
    }

    public void reverse(ListNode start, ListNode end) {
        end = end.next;
        // 逆转
        ListNode pre = null, cur = start, next = null;
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        start.next = end;
    }
    public ListNode getKGroupEnd(ListNode start, int k) {
        while (--k != 0 && start != null) {
            start = start.next;
        }
        return start;// 不满k个一组的时候，start = null
    }
}

2.双链表的反转

已知双链表结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class DoubleNode {
    int val;
    DoubleNode next;
    DoubleNode last;

    public DoubleNode(int val) {
        this.val = val;
    }

    public DoubleNode(int val, DoubleNode next, DoubleNode last) {
        this.val = val;
        this.next = next;
        this.last = last;
    }
}

反转双链表的方法：

1
2
3
4
5
6
7
8
9
10
11

public static DoubleNode reverseDoubleNode(DoubleNode head) {
    DoubleNode pre = null, next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        head.last = next;
        pre = head;
        head = next;
    }
    return pre;
}

我也写了对数器，如下：

其中，对照的解法是使用数组逆序完成。

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
94
95
96
97
98
99
100
101
102
103
104
105
106

class DoubleNode {
    int val;
    DoubleNode next;
    DoubleNode last;

    public DoubleNode(int val) {
        this.val = val;
    }

    public DoubleNode(int val, DoubleNode next, DoubleNode last) {
        this.val = val;
        this.next = next;
        this.last = last;
    }
}
public class DoubleLinkedListTest {
    public static DoubleNode reverseDoubleNode(DoubleNode head) {
        DoubleNode pre = null, next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }


    // 数组转DoubleNode
    public static DoubleNode arrToDoubleNode(int[] arr) {
        if (arr == null || arr.length == 0) return null;
        // 至少1个节点
        DoubleNode head = new DoubleNode(arr[0]);
        DoubleNode cur = head,pre = null;
        // 至少2个节点
        for (int i = 1;i < arr.length;i++) {
            DoubleNode newNode = new DoubleNode(arr[i]);
            cur.next = newNode;
            cur.last = pre;
            pre = cur;
            cur = cur.next;
        }
        return head;
    }
    // 产生一个随机数组
    // 数组长度[0, maxLen - 1]
    // 数组每个元素值的范围[0, maxValue - 1]
    public static int[] randomArray(int maxLen, int maxValue) {
        int n = (int)(Math.random() * maxLen);
        if (n == 0) return  null;
        // 至少一个
        int[] arr = new int[n];
        for (int i = 0;i < n;i++) {
            arr[i] = (int)(Math.random() * maxLen);
        }
        return arr;
    }
    // 数组逆序
    public static int[] reverseArr(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1) return arr;
        int[] ans = new int[arr.length];
        for (int i = 0;i < arr.length;i++) {
            ans[i] = arr[arr.length - i - 1];
        }
        return ans;
    }

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

    // 对数器
    public static void main(String[] args) {
        int maxLen = 100;
        int maxValue = 300;
        int testTime = 100000;
        System.out.println("开始测试！！");
        for (int i = 0;i < testTime;i++) {
            int[] arr = randomArray(maxLen,maxValue);
            if (arr == null || arr.length == 0) continue;
            DoubleNode head = arrToDoubleNode(arr);
            DoubleNode ans1 = reverseDoubleNode(head);
            int[] arrReverse = reverseArr(arr);
            DoubleNode ans2 = arrToDoubleNode(arrReverse);
            // 对比两个结果，
            for (int j = 0;j < arr.length;j++) {
                if (ans1.val != ans2.val) {
                    System.out.println("出错了！！！");
                    break;
                }
                ans1 = ans1.next;
                ans2 = ans2.next;
            }
        }
        System.out.println("测试结束！！");
    }

}

3.用单链表实现队列

题意说明：

已有单链表结构：

1
2
3
4
5
6
7
8
9

class Node<V> {
    public V val;
    Node<V> next;

    public Node(V v) {
        val = v;
        next = null;
    }
}

需要实现MyQueue<V>，完成下面几个方法：

1
2
3
4
5

boolean isEmpty();
int getSize();
void offer(V value);
V poll();
V peek();

解法：维护三个变量，head、tail，size

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

public static class MyQueue<V> {
    private int size;
    private Node<V> head;
    private Node<V> tail;

    //    boolean isEmpty();
    //    int size();
    //    void offer(V value);
    //    V poll();
    //    V peek();
    public MyQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    public void offer(V v) {
        Node<V> cur = new Node<>(v);
        if (tail == null) { // 此时队列一定为空
            head = cur;
            tail = cur;
        } else { // 队列不为空
            tail.next = cur;
            tail = cur; // 或者写tail = tail.next;
        }
        size++;
    }

    public V poll() {
        V ans = null;
        if (head != null) {
            ans = head.val;
            head = head.next;
            size--;
        }
        if (head == null) {
            tail = null;
        }
        return ans;
    }
    public V peek() {
        V ans = null;
        if (head != null) {
            ans = head.val;
        }
        return ans;
    }

这种怎么写对数器呢？

参考下面的方法：对比是java自带的队列数据结构Queue<Integer> test = new LinkedList<>();

循环 testTime 次，每次随机执行以下三种操作中的一种：

  • offer 操作 (33% 概率): 随机生成一个整数 num，同时调用 myQueue.offer(num) 和 test.offer(num)，将这个数加入两个队列。
  • poll 操作 (33% 概率): 如果队列不为空，同时调用 myQueue.poll() 和 test.poll()，分别从两个队列中取出元素。然后比较这两个取出的元素是否相等。如果不相等，说明你的实现有错，程序会输出 “Oops!”。
  • peek 操作 (33% 概率): 如果队列不为空，同时调用 myQueue.peek() 和 test.peek()，分别查看两个队列的队首元素。然后比较这两个元素是否相等。如果不相等，同样输出 “Oops!”。

在每次循环开始时，都会比较 myQueue 和 test 的 isEmpty() 和 size() 方法的返回值。如果它们不一致，也说明实现有误，输出 “Oops!”。这能保证队列在操作前后的状态（是否为空、大小）是一致的。

在循环结束后，再次检查两个队列的大小是否相等。

使用一个 while 循环，将两个队列中的所有元素依次取出并进行比较。这确保了在测试过程中没有遗漏任何不匹配的数据。

完整测试代码如下：

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

public void testQueue() {
    MyQueue<Integer> myQueue = new MyQueue<>();
    Queue<Integer> test = new LinkedList<>();
    int maxValue = 10000;
    int testSize = 10000000;
    System.out.println("测试开始！！！");
    for (int i = 0;i < testSize;i++) {
        if (myQueue.isEmpty() != test.isEmpty()) {
            System.out.println("出错了！！！");
        }
        if (myQueue.getSize() != test.size()) {
            System.out.println("出错了！！！");
        }
        double decide = Math.random();
        if (decide < 0.33) {
            // 添加一个数
            int t = (int)(Math.random() * maxValue);
            myQueue.offer(t);
            test.add(t);
        } else {
            // poll  或者peek
            // 前提：队列非空
            if (!myQueue.isEmpty()) {
                if (decide < 0.66) {
                    // poll
                    int poll1 = myQueue.poll();
                    int poll2 = test.poll();
                    if (poll2 != poll1) {
                        System.out.println("出错了！！！");
                    }
                } else {
                    int peek1 = myQueue.peek();
                    int peek2 = test.peek();
                    if (peek2 != peek1) {
                        System.out.println("出错了！！！");
                    }
                }
            }
        }

    }
    // 弹出每个数，进行对比
    while (!myQueue.isEmpty()) {
        int t1 = myQueue.poll();
        int t2 = test.poll();
        if (t1 != t2) {
            System.out.println("出错了！！！");
        }
    }

    System.out.println("测试结束！！！");
}

4.用单链表结构实现栈

用下面的数据结构实现一个栈。

已有单链表结构：

1
2
3
4
5
6
7
8
9

class Node<V> {
    public V val;
    Node<V> next;

    public Node(V v) {
        val = v;
        next = null;
    }
}

需要实现MyStack<V>，完成下面几个方法：

1
2
3
4
5

boolean isEmpty();
int getSize();
void push(V v);
V pop();
V peek();

解法：使用2个变量即可，head 和size，进栈方法类似于头插法。

代码：

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

public static class MyStack<V> {
    private Node<V> head;
    private int size;

    public MyStack() {
        head = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    public void push(V v) {
        Node<V> cur = new Node<>(v);
        if (head == null) {
            head = cur;
        } else {
            cur.next = head;
            head = cur;
        }
        size++;
    }

    public V pop() {
        V ans = null;
        if (head != null) {
            ans = head.val;
            head = head.next;
            size--;
        }
        return ans;

    }

    public V peek() {
        V ans = null;
        if(head != null) {
            ans = head.val;
        }
        return ans;
    }
}

使用对数器进行验证：

将实现的 MyStack 的行为与一个已知正确的、标准库中的 Stack 进行同步对比。

在一个大循环中（testTime 次），两个栈会同步执行一系列随机操作。每次循环中，会根据一个随机数 decide 来决定执行哪种操作：

  • push（大约 33% 概率）：生成一个随机整数，同时 push 到两个栈中。
  • pop 或 peek（大约 66% 概率）：如果两个栈都不为空，则随机选择 pop 或 peek 操作。

循环结束后，代码会通过一个 while 循环将两个栈中的所有元素依次弹出并进行最后的对比，以确保在整个测试过程中没有任何遗漏的错误。

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

@Test
public void testStack() {
    MyStack<Integer> stack = new MyStack<>();
    Stack<Integer> test = new Stack<>();
    int maxValue = 100000;
    int testTime = 10000000;
    System.out.println("开始测试！！！");
    for (int i = 0;i < testTime;i++) {
        if (stack.isEmpty() != test.isEmpty()) {
            System.out.println("Oops!!!");
        }
        if (stack.getSize() != test.size()) {
            System.out.println("Oops!!");
        }
        double decide = Math.random();
        if (decide < 0.33) {
            // push
            int t = (int)(Math.random() * maxValue);
            stack.push(t);
            test.push(t);
        } else {
            // pop  或者  peek
            // 前提：栈不为空
            if (!stack.isEmpty()) {
                if (decide < 0.66) {
                    // pop
                    int pop1 = stack.pop();
                    int pop2 = test.pop();
                    if (pop1 != pop2) {
                        System.out.println("Oops!!!");
                    }
                } else {
                    // peek
                    int peek1 = stack.peek();
                    int peek2 = test.peek();
                    if (peek2 != peek1) {
                        System.out.println("Oops!!!");
                    }
                }
            }
        }
    }
    // 依次弹出，对比
    while (!stack.isEmpty()) {
        int pop1 = stack.pop();
        int pop2 = test.pop();
        if(pop1 != pop2) {
            System.out.println("Oops!!!");
        }
    }
    System.out.println("测试结束！！！");
}

5.用双链表实现双端队列

首先需要明确：单链表不支持双端队列（如果要求时间复杂度是O(1)）。

因为：如果对单链表维护head和tail2个指针，当在队列的尾部删除一个元素时，无法用O(1)的时间获得前一个节点（只能从head开始遍历，这样的话时间复杂度就是O(n)），所以用单链表实现双端队列不合适。所以用双链表实现。

题意说明：

已有双链表结构：

1
2
3
4
5
6
7
8
9
10
11

public static class Node<V> {
    V value;
    Node<V> last;
    Node<V> next;

    public Node(V value) {
        this.value = value;
        last = null;
        next = null;
    }
}

需要实现的双端队列MyDeque<V>的方法有：

1
2
3
4
5
6
7
8

boolean isEmpty();
int getSize();
void pushHead(V v);
void pushTail(V v);
V pollHead();
V pollTail();
V peekHead();
V peekTail();

解法：用双链表实现双端队列，需要准备3个变量，head、tail、size

poll方法要注意head==tail的处理

从队首添加 (pushHead):—-头插法

  • 创建新节点，并让它的 next 指向当前的 head。
  • 如果队列不为空，更新原 head 节点的 last 指针，让它指向新节点。
  • 最后，将 head 指针更新为新节点。
  • 这样，新节点就成为了新的队首。

从队尾添加 (pushTail):

  • 创建新节点，并让当前的 tail 的 next 指向新节点。
  • 更新新节点的 last 指针，让它指向原 tail。
  • 最后，将 tail 指针更新为新节点。

从队首移除 (pollHead):

  • 保存当前 head 的值作为返回值。
  • 将 head 指针更新为 head.next。
  • 更新新的 head 节点的 last 指针为 null，从而将旧的 head 从链表中“切断”。
  • 需要特别处理队列只有一个元素的情况，此时 head 和 tail 都需要置为 null。

从队尾移除 (pollTail):

  • 保存当前 tail 的值作为返回值。
  • 将 tail 指针更新为 tail.last。
  • 更新新的 tail 节点的 next 指针为 null，从而将旧的 tail 从链表中移除。
  • 同样需要处理只有一个元素的特殊情况。

代码如下：

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

public static class MyDeque<V> {
    private Node<V> head;
    private Node<V> tail;
    private int size;

    public MyDeque() {
        head = null;
        tail = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    public void pushHead(V v) {
        Node<V> cur = new Node<>(v);
        if (head == null) { // 此时队列为空
            head = cur;
            tail = cur;
        } else {
            cur.next = head;
            head.last = cur;
            head = cur;
        }
        size++;
    }

    public void pushTail(V v) {
        Node<V> cur = new Node<>(v);
        if (tail == null) { // 队列为空
            tail = cur;
            head = cur;
        } else {
            tail.next = cur;
            cur.last = tail;
            tail = cur;
        }
        size++;
    }

    public V pollHead() {
        V ans = null;
        if (head == null) {
            return ans;
        }
        size--;
        ans = head.value;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.last = null;
        }

        return ans;
    }

    public V pollTail() {
        V ans = null;
        if (tail == null) {
            return ans;
        }
        size--;
        ans = tail.value;
        if(tail == head) {
            tail = null;
            head = null;
        } else {
            tail = tail.last;
            tail.next = null;
        }
        return ans;
    }

    public V peekHead() {
        return head == null ? null : head.value;
    }

    public V peekTail() {
        return tail == null ? null : tail.value;
    }
}

对数器如下：对比的是java的内置双端队列结构 Deque<Integer> test = new LinkedList<>();

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

@Test
public void testDeque() {
    MyDeque<Integer> deque = new MyDeque<>();
    Deque<Integer> test = new LinkedList<>();
    int maxValue = 100000;
    int testTime = 10000000;
    System.out.println("测试开始！！！");
    for(int i = 0;i < testTime;i++) {
        if (deque.isEmpty() != test.isEmpty()) {
            System.out.println("Oops!!!");
        }
        if (deque.getSize() != test.size()) {
            System.out.println("Oops!!!");
        }
        double decide = Math.random();
        if (decide < 0.33) {
            // push
            int t = (int)(Math.random() * maxValue);
            if (Math.random() < 0.5) {
                // pushHead
                deque.pushHead(t);
                test.addFirst(t);
            } else {
                // pushTail
                deque.pushTail(t);
                test.addLast(t);
            }
        } else if (decide < 0.66) {
            // poll
            if (!deque.isEmpty()) {
                if (Math.random() < 0.5) {
                    // pollFirst
                    int poll1 = deque.pollHead();
                    int poll2 = test.pollFirst();
                    if (poll2 != poll1) {
                        System.out.println("Oops!!!");
                    }
                } else {
                    // pollLast
                    int poll1 = deque.pollTail();
                    int poll2 = test.pollLast();
                    if (poll2 != poll1) {
                        System.out.println("Oops!!!");
                    }
                }
            }
        } else {
            if (!deque.isEmpty()) {
                //peek
                if (Math.random() < 0.5) {
                    // peekFirst
                    int peek1 = deque.peekHead();
                    int peek2 = test.peekFirst();
                    if (peek1 != peek2) {
                        System.out.println("Oops!!!");
                    }
                } else {
                    // peekLast
                    int peek1 = deque.peekTail();
                    int peek2 = test.peekLast();
                    if (peek1 != peek2) {
                        System.out.println("Oops!!!");
                    }
                }
            }
        }
    }
    // 依次pollFirst
    while (!deque.isEmpty()) {
        int poll1 = deque.pollHead();
        int poll2 = test.pollFirst();
        if (poll1 != poll2) {
            System.out.println("Oops!!!");
        }
    }
    System.out.println("测试结束！！！");
}

6.两数之和-力扣第2题

https://leetcode.cn/problems/add-two-numbers/

解法：分为3个步骤，首先找到长度长的链表是哪个，长度短的链表是哪个。

阶段1:长链表和短链表都不是null curL.val + curS + carry

阶段2:短链表是null，长链表不是null curL.val + carry

阶段3:carry不是0，最后再加一个节点（值为1）

需要准备一个last节点跟踪，便于阶段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

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int l1Len = listLen(l1);
    int l2Len = listLen(l2);
    ListNode l = l1Len >= l2Len ? l1 : l2;
    ListNode curL = l, curS = l == l1 ? l2 : l1;
    int carry = 0, curNum = 0;
    ListNode last = curL;
    while (curS != null) {
        curNum = curL.val + curS.val + carry;
        curL.val = curNum % 10;
        carry = curNum / 10;
        last = curL;
        curL = curL.next;
        curS = curS.next;
    }

    while (curL != null) {
        curNum = curL.val + carry;
        curL.val = curNum % 10;
        carry = curNum / 10;
        last = curL;
        curL = curL.next;
    }

    if (carry != 0) {
        last.next = new ListNode(1);
    }
    return l;
}

public int listLen(ListNode l) {
    int ans = 0;
    while (l != null) {
        ans++;
        l = l.next;
    }
    return ans;
}

image-20250905231335405

对数器：

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

public ListNode numToListNode(int num) {
    if (num == 0) return null;
    ListNode head = new ListNode(num % 10);
    ListNode cur = head;
    num = num / 10;
    while (num != 0) {
        cur.next = new ListNode(num % 10);
        cur = cur.next;
        num = num / 10;
    }
    return head;
}

// 对数器
@Test
public void testAddTwoNums() {
    int maxValue = 100000;
    int testTime = 10000000;
    System.out.println("开始测试！！！");
    for (int i = 0;i < testTime;i++) {
        int num1 = (int)(Math.random() * maxValue);
        int num2 = (int)(Math.random() * maxValue);
        // 求出标准答案
        int anticipateAns = num1 + num2;
        // num1, num2, anticipateAns都转成链表
        // 比如123转换成链表3-->2-->1
        ListNode l1 = numToListNode(num1);
        ListNode l2 = numToListNode(num2);
        ListNode anticipateListNode = numToListNode(anticipateAns);

        ListNode ans = addTwoNumbers(l1, l2);
        while (ans != null) {
            if (ans.val != anticipateListNode.val) {
                System.out.println("Oops!!!");
                break;
            }
            ans = ans.next;
            anticipateListNode = anticipateListNode.next;
        }

    }
    System.out.println("结束测试！！！");

}

7.合并2个有序链表

力扣21题：https://leetcode.cn/problems/merge-two-sorted-lists/

牛客（填函数风格）：https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=295

牛客（ACM风格）：https://www.nowcoder.com/practice/98a51a92836e4861be1803aaa9037440

填函数风格：

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode head = list1.val <= list2.val ? list1 : list2;
        ListNode cur1 = head.next;
        ListNode cur2 = head == list1 ? list2 : list1;
        ListNode pre = head;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }
}

ACM 风格：https://www.nowcoder.com/practice/98a51a92836e4861be1803aaa9037440

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

import java.util.Scanner;
import java.io.*;

class ListNode{
    int val;
    ListNode next;
    public ListNode(int v) {
        this.val = v;
        this.next = null;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int len1 = (int)in.nval;
            in.nextToken();
            ListNode l1 = null, l2 = null;
            if (len1 != 0) {
                l1 = new ListNode((int)in.nval);
                in.nextToken();
                ListNode cur1 = l1;
                for (int i = 1;i < len1;i++) {
                    cur1.next = new ListNode((int)in.nval);
                    in.nextToken();
                    cur1 = cur1.next;
                }
            } 
            int len2 = (int)in.nval;
            in.nextToken();
            if (len2 != 0) {
                l2 = new ListNode((int)in.nval);
                in.nextToken();
                ListNode cur2 = l2;
                for (int i = 1;i < len2;i++) {
                    cur2.next = new ListNode((int)in.nval);
                    in.nextToken();
                    cur2 = cur2.next;
                }
            }
            ListNode ans = merge(l1, l2);
            while (ans != null) {
                out.print(ans.val + " ");
                ans = ans.next;
            }

        }
        out.flush();
        br.close();
        out.close();
    }

    public static ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode head = l1.val <= l2.val ? l1 : l2;
        ListNode pre = head;
        ListNode cur1 = head.next;
        ListNode cur2 = head == l1 ? l2 : l1;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }
}
CATALOG
    FEATURED TAGS
    书籍阅读 算法 人工智能AI基础 python基础 力扣 numpy pandas 机器学习-吴恩达 机器学习算法 matplotlib spring6 Java基础 java集合 ollama工具 python爬虫
    FRIENDS