朱继鹏的博客

天道酬勤，全栈不停

0%

algorithm-link

发表于 更新于 分类于
链表算法

简单

环形链表

题目描述

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
给你一个链表的头结点 head ，判断链表中是否有环。

如果链表中有某个结点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

 

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个结点。
示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个结点。
示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
 

提示：

链表中结点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -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
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }

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

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }

            slow = slow.next;
            fast = fast.next.next;
        }

        return true;

        // Set<ListNode> seen = new HashSet<ListNode>();
        // while (head != null) {
        // if (!seen.add(head)) {
        // return true;
        // }
        // head = head.next;
        // }
        // return false;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public static ListNode genLinkedList(int[] nums, boolean withHead, int loopPos) {
            if (nums.length == 0) {
                return null;
            }

            int val = withHead ? Integer.MIN_VALUE : nums[0];
            ListNode head = new ListNode(val);

            ListNode loop = withHead ? null : loopPos == 0 ? head : null;

            int b = withHead ? 0 : 1;
            ListNode p = head;
            for (int i = b; i < nums.length; i++) {
                p.next = new ListNode(nums[i]);
                p = p.next;

                if (loopPos == i) {
                    loop = p;
                }
            }

            if (loop != null) {
                p.next = loop;
            }

            return head;
        }

        public static ListNode genLinkedListWithHeadNode(int[] nums) {
            return genLinkedList(nums, true, -1);
        }

        public static ListNode genLinkedListWithoutHeadNode(int[] nums) {
            return genLinkedList(nums, false, -1);
        }

        public static ListNode genLoopedLinkedListWithHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, true, pos);
        }

        public static ListNode genLoopedLinkedListWithoutHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, false, pos);
        }

        public static int getCount(ListNode head, boolean withHead) {
            ListNode p = withHead ? head.next : head;

            int c = 0;
            while (p != null) {
                c++;
                p = p.next;
            }

            return c;
        }

        public static int[] toArray(ListNode head, boolean withHead) {
            int c = getCount(head, withHead);
            int[] nums = new int[c];

            ListNode p = withHead ? head.next : head;

            int k = 0;
            while (p != null) {
                nums[k] = p.val;

                k++;
                p = p.next;
            }

            return nums;
        }

        public static int[] toArrayWithHeadNode(ListNode head) {
            return toArray(head, true);
        }

        public static int[] toArrayWithoutHeadNode(ListNode head) {
            return toArray(head, false);
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        int[] nums = { 3, 2, 0, -4 };
        int pos = 1;

        ListNode head = ListNode.genLoopedLinkedListWithoutHeadNode(nums, pos);
        boolean result = new Solution().hasCycle(head);
        System.out.println(result);
    }

    public static void testCase2() {
        int[] nums = { 1, 2 };
        int pos = 0;

        ListNode head = ListNode.genLoopedLinkedListWithoutHeadNode(nums, pos);
        boolean result = new Solution().hasCycle(head);
        System.out.println(result);
    }

    public static void testCase3() {
        int[] nums = { 1 };
        int pos = -1;

        ListNode head = ListNode.genLoopedLinkedListWithoutHeadNode(nums, pos);
        boolean result = new Solution().hasCycle(head);
        System.out.println(result);
    }
}

两数相加

题目描述

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
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个结点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

 

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
 

提示：

每个链表中的结点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

题目解答

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);

        ListNode t = dummy; // 保存新链表的末尾

        int carry = 0;

        ListNode p = l1;
        ListNode q = l2;
        while (p != null || q != null) {
            int x = p == null ? 0 : p.val;
            int y = q == null ? 0 : q.val;
            int value = x + y + carry;

            carry = value > 9 ? 1 : 0;
            value = value > 9 ? value - 10 : value;

            t.next = new ListNode(value);
            t = t.next;

            p = p == null ? p : p.next;
            q = q == null ? q : q.next;
        }

        if (carry > 0) {
            int value = carry;

            t.next = new ListNode(value);
            t = t.next;
        }

        return dummy.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public static ListNode genLinkedList(int[] nums, boolean withHead, int loopPos) {
            if (nums.length == 0) {
                return null;
            }

            int val = withHead ? Integer.MIN_VALUE : nums[0];
            ListNode head = new ListNode(val);

            ListNode loop = withHead ? null : loopPos == 0 ? head : null;

            int b = withHead ? 0 : 1;
            ListNode p = head;
            for (int i = b; i < nums.length; i++) {
                p.next = new ListNode(nums[i]);
                p = p.next;

                if (loopPos == i) {
                    loop = p;
                }
            }

            if (loop != null) {
                p.next = loop;
            }

            return head;
        }

        public static ListNode genLinkedListWithHeadNode(int[] nums) {
            return genLinkedList(nums, true, -1);
        }

        public static ListNode genLinkedListWithoutHeadNode(int[] nums) {
            return genLinkedList(nums, false, -1);
        }

        public static ListNode genLoopedLinkedListWithHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, true, pos);
        }

        public static ListNode genLoopedLinkedListWithoutHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, false, pos);
        }

        public static int getCount(ListNode head, boolean withHead) {
            ListNode p = withHead ? head.next : head;

            int c = 0;
            while (p != null) {
                c++;
                p = p.next;
            }

            return c;
        }

        public static int[] toArray(ListNode head, boolean withHead) {
            int c = getCount(head, withHead);
            int[] nums = new int[c];

            ListNode p = withHead ? head.next : head;

            int k = 0;
            while (p != null) {
                nums[k] = p.val;

                k++;
                p = p.next;
            }

            return nums;
        }

        public static int[] toArrayWithHeadNode(ListNode head) {
            return toArray(head, true);
        }

        public static int[] toArrayWithoutHeadNode(ListNode head) {
            return toArray(head, false);
        }
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        int[] nums1 = { 2, 4, 3 };
        int[] nums2 = { 5, 6, 4 };

        ListNode l1 = ListNode.genLinkedListWithoutHeadNode(nums1);
        ListNode l2 = ListNode.genLinkedListWithoutHeadNode(nums2);
        ListNode result = new Solution().addTwoNumbers(l1, l2);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase2() {
        int[] nums1 = { 0 };
        int[] nums2 = { 0 };

        ListNode l1 = ListNode.genLinkedListWithoutHeadNode(nums1);
        ListNode l2 = ListNode.genLinkedListWithoutHeadNode(nums2);
        ListNode result = new Solution().addTwoNumbers(l1, l2);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase3() {
        int[] nums1 = { 9, 9, 9, 9, 9, 9, 9 };
        int[] nums2 = { 9, 9, 9, 9 };

        ListNode l1 = ListNode.genLinkedListWithoutHeadNode(nums1);
        ListNode l2 = ListNode.genLinkedListWithoutHeadNode(nums2);
        ListNode result = new Solution().addTwoNumbers(l1, l2);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }
}

合并两个有序链表

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。 

 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]
 

提示：

两个链表的结点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

题目解答

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);

        ListNode t = dummy; // 保存新链表的末尾

        ListNode p = list1;
        ListNode q = list2;
        while (p != null && q != null) {
            while (p != null && q != null && p.val <= q.val) {
                t.next = new ListNode(p.val);
                t = t.next;

                p = p.next;
            }

            while (p != null && q != null && q.val <= p.val) {
                t.next = new ListNode(q.val);
                t = t.next;

                q = q.next;
            }
        }

        while (p != null) {
            t.next = new ListNode(p.val);
            t = t.next;

            p = p.next;
        }

        while (q != null) {
            t.next = new ListNode(q.val);
            t = t.next;

            q = q.next;
        }

        return dummy.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public static ListNode genLinkedList(int[] nums, boolean withHead, int loopPos) {
            if (nums.length == 0) {
                return null;
            }

            int val = withHead ? Integer.MIN_VALUE : nums[0];
            ListNode head = new ListNode(val);

            ListNode loop = withHead ? null : loopPos == 0 ? head : null;

            int b = withHead ? 0 : 1;
            ListNode p = head;
            for (int i = b; i < nums.length; i++) {
                p.next = new ListNode(nums[i]);
                p = p.next;

                if (loopPos == i) {
                    loop = p;
                }
            }

            if (loop != null) {
                p.next = loop;
            }

            return head;
        }

        public static ListNode genLinkedListWithHeadNode(int[] nums) {
            return genLinkedList(nums, true, -1);
        }

        public static ListNode genLinkedListWithoutHeadNode(int[] nums) {
            return genLinkedList(nums, false, -1);
        }

        public static ListNode genLoopedLinkedListWithHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, true, pos);
        }

        public static ListNode genLoopedLinkedListWithoutHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, false, pos);
        }

        public static int getCount(ListNode head, boolean withHead) {
            ListNode p = withHead ? head.next : head;

            int c = 0;
            while (p != null) {
                c++;
                p = p.next;
            }

            return c;
        }

        public static int[] toArray(ListNode head, boolean withHead) {
            int c = getCount(head, withHead);
            int[] nums = new int[c];

            ListNode p = withHead ? head.next : head;

            int k = 0;
            while (p != null) {
                nums[k] = p.val;

                k++;
                p = p.next;
            }

            return nums;
        }

        public static int[] toArrayWithHeadNode(ListNode head) {
            return toArray(head, true);
        }

        public static int[] toArrayWithoutHeadNode(ListNode head) {
            return toArray(head, false);
        }
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        int[] nums1 = { 1, 2, 4 };
        int[] nums2 = { 1, 3, 4 };

        ListNode l1 = ListNode.genLinkedListWithoutHeadNode(nums1);
        ListNode l2 = ListNode.genLinkedListWithoutHeadNode(nums2);
        ListNode result = new Solution().mergeTwoLists(l1, l2);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase2() {
        int[] nums1 = {};
        int[] nums2 = {};

        ListNode l1 = ListNode.genLinkedListWithoutHeadNode(nums1);
        ListNode l2 = ListNode.genLinkedListWithoutHeadNode(nums2);
        ListNode result = new Solution().mergeTwoLists(l1, l2);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase3() {
        int[] nums1 = {};
        int[] nums2 = { 0 };

        ListNode l1 = ListNode.genLinkedListWithoutHeadNode(nums1);
        ListNode l2 = ListNode.genLinkedListWithoutHeadNode(nums2);
        ListNode result = new Solution().mergeTwoLists(l1, l2);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }
}

随机链表的复制

题目描述

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
给你一个长度为 n 的链表，每个结点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何结点或空结点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 结点组成，其中每个新结点的值都设为其对应的原结点的值。新结点的 next 指针和 random 指针也都应指向复制链表中的新结点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的结点 。

例如，如果原链表中有 X 和 Y 两个结点，其中 X.random --> Y 。那么在复制链表中对应的两个结点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头结点。

用一个由 n 个结点组成的链表来表示输入/输出中的链表。每个结点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的结点索引（范围从 0 到 n-1）；如果不指向任何结点，则为  null 。
你的代码 只 接受原链表的头结点 head 作为传入参数。

 

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
 

提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的结点。

题目解答

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> caches = new HashMap<>();

        Node p = head;
        while (p != null) {
            Node node = new Node(p.val);
            caches.put(p, node);

            p = p.next;
        }

        p = head;
        while (p != null) {
            Node node = caches.get(p);
            if (p.next != null) {
                node.next = caches.get(p.next);
            }
            if (p.random != null) {
                node.random = caches.get(p.random);
            }

            p = p.next;
        }

        return caches.get(head);
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

        public static Node genLinkedList(int[][] arrays) {
            if (arrays.length == 0) {
                return null;
            }

            Node[] caches = new Node[arrays.length];

            for (int i = 0; i < arrays.length; i++) {
                int v = arrays[i][0];
                caches[i] = new Node(v);
            }

            for (int i = 0; i < arrays.length; i++) {
                Node node = caches[i];

                int j = i + 1;
                if (j < arrays.length) {
                    node.next = caches[j];
                }

                int k = arrays[i][1];
                if (k >= 0) {
                    node.random = caches[k];
                }
            }

            return caches[0];
        }

        public static Map<Node, Integer> getIndexMap(Node head) {
            Map<Node, Integer> map = new HashMap<>();

            int index = 0;

            Node p = head;
            while (p != null) {
                map.put(p, index++);
                p = p.next;
            }

            return map;
        }

        public static void printLinkedList(Node head) {
            Map<Node, Integer> indexMap = getIndexMap(head);

            Node p = head;
            while (p != null) {
                String nodeValue = p.val + "";
                String randomValue = p.random != null ? p.random.val + "" : "null";
                String randomIndex = p.random != null ? indexMap.get(p.random) + "" : "-1";

                String s = String.format("node: %25s => [%5s], random: %25s => [%5s], randomIndex: %s",
                        p, nodeValue, p.random, randomValue, randomIndex);
                System.out.println(s);

                p = p.next;
            }
        }

        public static void printResult(Node head, Node result) {
            System.out.println("--->");
            Node.printLinkedList(head);
            System.out.println();
            Node.printLinkedList(result);
            System.out.println("<---");
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        int[][] arrays = {
                { 7, -1 },
                { 13, 0 },
                { 11, 4 },
                { 10, 2 },
                { 1, 0 }
        };

        Node head = Node.genLinkedList(arrays);
        Node result = new Solution().copyRandomList(head);

        Node.printResult(head, result);
    }

    public static void testCase2() {
        int[][] arrays = {
                { 1, 1 },
                { 2, 1 }
        };

        Node head = Node.genLinkedList(arrays);
        Node result = new Solution().copyRandomList(head);

        Node.printResult(head, result);
    }

    public static void testCase3() {
        int[][] arrays = {
                { 3, -1 },
                { 3, 0 },
                { 3, -1 }
        };

        Node head = Node.genLinkedList(arrays);
        Node result = new Solution().copyRandomList(head);

        Node.printResult(head, result);
    }
}

其他解法

解法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
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> caches = new HashMap<>();

        return copyNode(head, caches);
    }

    private Node copyNode(Node node, Map<Node, Node> caches) {
        if (node == null) {
            return null;
        }

        Node newNode = caches.get(node);
        if (newNode != null) {
            return newNode;
        }

        newNode = new Node(node.val);

        caches.put(node, newNode);

        newNode.next = copyNode(node.next, caches);
        newNode.random = copyNode(node.random, caches);

        return newNode;
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

        public static Node genLinkedList(int[][] arrays) {
            if (arrays.length == 0) {
                return null;
            }

            Node[] caches = new Node[arrays.length];

            for (int i = 0; i < arrays.length; i++) {
                int v = arrays[i][0];
                caches[i] = new Node(v);
            }

            for (int i = 0; i < arrays.length; i++) {
                Node node = caches[i];

                int j = i + 1;
                if (j < arrays.length) {
                    node.next = caches[j];
                }

                int k = arrays[i][1];
                if (k >= 0) {
                    node.random = caches[k];
                }
            }

            return caches[0];
        }

        public static Map<Node, Integer> getIndexMap(Node head) {
            Map<Node, Integer> map = new HashMap<>();

            int index = 0;

            Node p = head;
            while (p != null) {
                map.put(p, index++);
                p = p.next;
            }

            return map;
        }

        public static void printLinkedList(Node head) {
            Map<Node, Integer> indexMap = getIndexMap(head);

            Node p = head;
            while (p != null) {
                String nodeValue = p.val + "";
                String randomValue = p.random != null ? p.random.val + "" : "null";
                String randomIndex = p.random != null ? indexMap.get(p.random) + "" : "-1";

                String s = String.format("node: %25s => [%5s], random: %25s => [%5s], randomIndex: %s",
                        p, nodeValue, p.random, randomValue, randomIndex);
                System.out.println(s);

                p = p.next;
            }
        }

        public static void printResult(Node head, Node result) {
            System.out.println("--->");
            Node.printLinkedList(head);
            System.out.println();
            Node.printLinkedList(result);
            System.out.println("<---");
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        int[][] arrays = {
                { 7, -1 },
                { 13, 0 },
                { 11, 4 },
                { 10, 2 },
                { 1, 0 }
        };

        Node head = Node.genLinkedList(arrays);
        Node result = new Solution().copyRandomList(head);

        Node.printResult(head, result);
    }

    public static void testCase2() {
        int[][] arrays = {
                { 1, 1 },
                { 2, 1 }
        };

        Node head = Node.genLinkedList(arrays);
        Node result = new Solution().copyRandomList(head);

        Node.printResult(head, result);
    }

    public static void testCase3() {
        int[][] arrays = {
                { 3, -1 },
                { 3, 0 },
                { 3, -1 }
        };

        Node head = Node.genLinkedList(arrays);
        Node result = new Solution().copyRandomList(head);

        Node.printResult(head, result);
    }
}

解法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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
import java.util.HashMap;
import java.util.Map;

public class Solution {
    Map<Node, Node> caches = new HashMap<>();

    public Node copyRandomList(Node head) {
        Node node = head;
        if (node == null) {
            return null;
        }

        Node newNode = caches.get(node);
        if (newNode != null) {
            return newNode;
        }

        newNode = new Node(node.val);

        caches.put(node, newNode);

        newNode.next = copyRandomList(node.next);
        newNode.random = copyRandomList(node.random);

        return newNode;
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

        public static Node genLinkedList(int[][] arrays) {
            if (arrays.length == 0) {
                return null;
            }

            Node[] caches = new Node[arrays.length];

            for (int i = 0; i < arrays.length; i++) {
                int v = arrays[i][0];
                caches[i] = new Node(v);
            }

            for (int i = 0; i < arrays.length; i++) {
                Node node = caches[i];

                int j = i + 1;
                if (j < arrays.length) {
                    node.next = caches[j];
                }

                int k = arrays[i][1];
                if (k >= 0) {
                    node.random = caches[k];
                }
            }

            return caches[0];
        }

        public static Map<Node, Integer> getIndexMap(Node head) {
            Map<Node, Integer> map = new HashMap<>();

            int index = 0;

            Node p = head;
            while (p != null) {
                map.put(p, index++);
                p = p.next;
            }

            return map;
        }

        public static void printLinkedList(Node head) {
            Map<Node, Integer> indexMap = getIndexMap(head);

            Node p = head;
            while (p != null) {
                String nodeValue = p.val + "";
                String randomValue = p.random != null ? p.random.val + "" : "null";
                String randomIndex = p.random != null ? indexMap.get(p.random) + "" : "-1";

                String s = String.format("node: %25s => [%5s], random: %25s => [%5s], randomIndex: %s",
                        p, nodeValue, p.random, randomValue, randomIndex);
                System.out.println(s);

                p = p.next;
            }
        }

        public static void printResult(Node head, Node result) {
            System.out.println("--->");
            Node.printLinkedList(head);
            System.out.println();
            Node.printLinkedList(result);
            System.out.println("<---");
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        int[][] arrays = {
                { 7, -1 },
                { 13, 0 },
                { 11, 4 },
                { 10, 2 },
                { 1, 0 }
        };

        Node head = Node.genLinkedList(arrays);
        Node result = new Solution().copyRandomList(head);

        Node.printResult(head, result);
    }

    public static void testCase2() {
        int[][] arrays = {
                { 1, 1 },
                { 2, 1 }
        };

        Node head = Node.genLinkedList(arrays);
        Node result = new Solution().copyRandomList(head);

        Node.printResult(head, result);
    }

    public static void testCase3() {
        int[][] arrays = {
                { 3, -1 },
                { 3, 0 },
                { 3, -1 }
        };

        Node head = Node.genLinkedList(arrays);
        Node result = new Solution().copyRandomList(head);

        Node.printResult(head, result);
    }
}

解法3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}

反转链表II

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表结点，返回 反转后的链表 。
 

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]
 

提示：

链表中结点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

题目解答

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }

        ListNode dummy = new ListNode(0);

        ListNode t1 = dummy; // 保存合并时第1个链表的末尾
        ListNode t2 = null; // 保存合并时第2个链表的末尾

        // 移动p到left
        ListNode p = head;
        for (int i = 1; i < left; i++) {
            if (p == null) {
                break;
            }

            if (i == left - 1) {
                t2 = p;
            }

            p = p.next;
        }

        if (t2 != null) {
            ListNode l = head;

            t1.next = l;
            t1 = t2;
        }

        ListNode l = null;
        t2 = p;
        for (int i = left; i <= right; i++) {
            if (p == null) {
                break;
            }

            // 先保存旧链表的剩余部分
            ListNode q = p.next;

            // 在新链表的头部插入
            p.next = l;
            l = p;

            // 继续处理旧链表的剩余部分
            p = q;
        }

        if (t2 != null) {
            t1.next = l;
            t1 = t2;
        }

        t1.next = p;

        return dummy.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public static ListNode genLinkedList(int[] nums, boolean withHead, int loopPos) {
            if (nums.length == 0) {
                return null;
            }

            int val = withHead ? Integer.MIN_VALUE : nums[0];
            ListNode head = new ListNode(val);

            ListNode loop = withHead ? null : loopPos == 0 ? head : null;

            int b = withHead ? 0 : 1;
            ListNode p = head;
            for (int i = b; i < nums.length; i++) {
                p.next = new ListNode(nums[i]);
                p = p.next;

                if (loopPos == i) {
                    loop = p;
                }
            }

            if (loop != null) {
                p.next = loop;
            }

            return head;
        }

        public static ListNode genLinkedListWithHeadNode(int[] nums) {
            return genLinkedList(nums, true, -1);
        }

        public static ListNode genLinkedListWithoutHeadNode(int[] nums) {
            return genLinkedList(nums, false, -1);
        }

        public static ListNode genLoopedLinkedListWithHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, true, pos);
        }

        public static ListNode genLoopedLinkedListWithoutHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, false, pos);
        }

        public static int getCount(ListNode head, boolean withHead) {
            ListNode p = withHead ? head.next : head;

            int c = 0;
            while (p != null) {
                c++;
                p = p.next;
            }

            return c;
        }

        public static int[] toArray(ListNode head, boolean withHead) {
            int c = getCount(head, withHead);
            int[] nums = new int[c];

            ListNode p = withHead ? head.next : head;

            int k = 0;
            while (p != null) {
                nums[k] = p.val;

                k++;
                p = p.next;
            }

            return nums;
        }

        public static int[] toArrayWithHeadNode(ListNode head) {
            return toArray(head, true);
        }

        public static int[] toArrayWithoutHeadNode(ListNode head) {
            return toArray(head, false);
        }
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        int[] nums = { 1, 2, 3, 4, 5 };
        int left = 2;
        int right = 4;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().reverseBetween(link, left, right);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase2() {
        int[] nums = { 3, 5 };
        int left = 1;
        int right = 1;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().reverseBetween(link, left, right);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase3() {
        int[] nums = { 3, 5 };
        int left = 1;
        int right = 2;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().reverseBetween(link, left, right);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }
}

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
给你链表的头结点 head ，每 k 个结点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果结点总数不是 k 的整数倍，那么请将最后剩余的结点保持原有顺序。

你不能只是单纯的改变结点内部的值，而是需要实际进行结点交换。

 

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

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

提示：
链表中的结点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
 

进阶：你可以设计一个只用 O(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
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);

        ListNode t1 = dummy; // 保存合并时第1个链表的末尾
        ListNode t2 = null; // 保存合并时第2个链表的末尾

        ListNode p = head;
        while (p != null) {
            t2 = p;

            ListNode r = p;
            for (int i = 0; i < k; i++) {
                if (r == null) {
                    ListNode l = p;

                    t1.next = l;
                    t1 = t2;

                    return dummy.next;
                }

                r = r.next;
            }

            ListNode l = null;
            for (int i = 0; i < k; i++) {
                if (p == null) {
                    break;
                }

                // 先保存旧链表的剩余部分
                ListNode q = p.next;

                // 在新链表的头部插入
                p.next = l;
                l = p;

                // 继续处理旧链表的剩余部分
                p = q;
            }

            t1.next = l;
            t1 = t2;
        }

        return dummy.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public static ListNode genLinkedList(int[] nums, boolean withHead, int loopPos) {
            if (nums.length == 0) {
                return null;
            }

            int val = withHead ? Integer.MIN_VALUE : nums[0];
            ListNode head = new ListNode(val);

            ListNode loop = withHead ? null : loopPos == 0 ? head : null;

            int b = withHead ? 0 : 1;
            ListNode p = head;
            for (int i = b; i < nums.length; i++) {
                p.next = new ListNode(nums[i]);
                p = p.next;

                if (loopPos == i) {
                    loop = p;
                }
            }

            if (loop != null) {
                p.next = loop;
            }

            return head;
        }

        public static ListNode genLinkedListWithHeadNode(int[] nums) {
            return genLinkedList(nums, true, -1);
        }

        public static ListNode genLinkedListWithoutHeadNode(int[] nums) {
            return genLinkedList(nums, false, -1);
        }

        public static ListNode genLoopedLinkedListWithHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, true, pos);
        }

        public static ListNode genLoopedLinkedListWithoutHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, false, pos);
        }

        public static int getCount(ListNode head, boolean withHead) {
            ListNode p = withHead ? head.next : head;

            int c = 0;
            while (p != null) {
                c++;
                p = p.next;
            }

            return c;
        }

        public static int[] toArray(ListNode head, boolean withHead) {
            int c = getCount(head, withHead);
            int[] nums = new int[c];

            ListNode p = withHead ? head.next : head;

            int k = 0;
            while (p != null) {
                nums[k] = p.val;

                k++;
                p = p.next;
            }

            return nums;
        }

        public static int[] toArrayWithHeadNode(ListNode head) {
            return toArray(head, true);
        }

        public static int[] toArrayWithoutHeadNode(ListNode head) {
            return toArray(head, false);
        }
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 1, 2, 3, 4, 5 };
        int k = 2;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().reverseKGroup(link, k);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase2() {
        int[] nums = { 1, 2, 3, 4, 5 };
        int k = 3;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().reverseKGroup(link, k);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }
}

删除链表的倒数第N个结点

题目描述

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
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]
 

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
 

进阶：你能尝试使用一趟扫描实现吗？

题目解答

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        int c = 0;

        ListNode p = head;
        while (p != null) {
            c++;
            p = p.next;
        }

        if (n > c) {
            return dummy.next;
        }

        p = dummy;

        int m = c - n;
        for (int i = 0; i < m; i++) {
            p = p.next;
        }

        p.next = p.next.next;

        return dummy.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public static ListNode genLinkedList(int[] nums, boolean withHead, int loopPos) {
            if (nums.length == 0) {
                return null;
            }

            int val = withHead ? Integer.MIN_VALUE : nums[0];
            ListNode head = new ListNode(val);

            ListNode loop = withHead ? null : loopPos == 0 ? head : null;

            int b = withHead ? 0 : 1;
            ListNode p = head;
            for (int i = b; i < nums.length; i++) {
                p.next = new ListNode(nums[i]);
                p = p.next;

                if (loopPos == i) {
                    loop = p;
                }
            }

            if (loop != null) {
                p.next = loop;
            }

            return head;
        }

        public static ListNode genLinkedListWithHeadNode(int[] nums) {
            return genLinkedList(nums, true, -1);
        }

        public static ListNode genLinkedListWithoutHeadNode(int[] nums) {
            return genLinkedList(nums, false, -1);
        }

        public static ListNode genLoopedLinkedListWithHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, true, pos);
        }

        public static ListNode genLoopedLinkedListWithoutHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, false, pos);
        }

        public static int getCount(ListNode head, boolean withHead) {
            ListNode p = withHead ? head.next : head;

            int c = 0;
            while (p != null) {
                c++;
                p = p.next;
            }

            return c;
        }

        public static int[] toArray(ListNode head, boolean withHead) {
            int c = getCount(head, withHead);
            int[] nums = new int[c];

            ListNode p = withHead ? head.next : head;

            int k = 0;
            while (p != null) {
                nums[k] = p.val;

                k++;
                p = p.next;
            }

            return nums;
        }

        public static int[] toArrayWithHeadNode(ListNode head) {
            return toArray(head, true);
        }

        public static int[] toArrayWithoutHeadNode(ListNode head) {
            return toArray(head, false);
        }
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
        testCase4();
        testCase5();
    }

    public static void testCase1() {
        int[] nums = { 1, 2, 3, 4, 5 };
        int k = 2;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().removeNthFromEnd(link, k);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase2() {
        int[] nums = { 1 };
        int k = 1;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().removeNthFromEnd(link, k);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase3() {
        int[] nums = { 1 };
        int k = 2;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().removeNthFromEnd(link, k);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase4() {
        int[] nums = { 1, 2 };
        int k = 1;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().removeNthFromEnd(link, k);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase5() {
        int[] nums = { 1, 2 };
        int k = 2;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().removeNthFromEnd(link, k);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }
}

其他解法

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

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

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的结点，只留下不同的数字 。返回 已排序的链表 。

 

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]
 

提示：

链表中结点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

题目解答

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);

        ListNode t1 = dummy; // 保存合并时第1个链表的末尾
        ListNode t2 = null; // 保存合并时第2个链表的末尾

        ListNode p = head;
        while (p != null) {
            int c = 0;
            int first = p.val;
            t2 = p;
            while (p != null && p.val == first) {
                c++;

                // t2 = p;
                p = p.next;
            }

            if (c != 1) {
                continue;
            }

            ListNode l = t2;
            // 只取一个结点
            l.next = null;

            t1.next = l;
            t1 = t2;
        }

        return dummy.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public static ListNode genLinkedList(int[] nums, boolean withHead, int loopPos) {
            if (nums.length == 0) {
                return null;
            }

            int val = withHead ? Integer.MIN_VALUE : nums[0];
            ListNode head = new ListNode(val);

            ListNode loop = withHead ? null : loopPos == 0 ? head : null;

            int b = withHead ? 0 : 1;
            ListNode p = head;
            for (int i = b; i < nums.length; i++) {
                p.next = new ListNode(nums[i]);
                p = p.next;

                if (loopPos == i) {
                    loop = p;
                }
            }

            if (loop != null) {
                p.next = loop;
            }

            return head;
        }

        public static ListNode genLinkedListWithHeadNode(int[] nums) {
            return genLinkedList(nums, true, -1);
        }

        public static ListNode genLinkedListWithoutHeadNode(int[] nums) {
            return genLinkedList(nums, false, -1);
        }

        public static ListNode genLoopedLinkedListWithHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, true, pos);
        }

        public static ListNode genLoopedLinkedListWithoutHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, false, pos);
        }

        public static int getCount(ListNode head, boolean withHead) {
            ListNode p = withHead ? head.next : head;

            int c = 0;
            while (p != null) {
                c++;
                p = p.next;
            }

            return c;
        }

        public static int[] toArray(ListNode head, boolean withHead) {
            int c = getCount(head, withHead);
            int[] nums = new int[c];

            ListNode p = withHead ? head.next : head;

            int k = 0;
            while (p != null) {
                nums[k] = p.val;

                k++;
                p = p.next;
            }

            return nums;
        }

        public static int[] toArrayWithHeadNode(ListNode head) {
            return toArray(head, true);
        }

        public static int[] toArrayWithoutHeadNode(ListNode head) {
            return toArray(head, false);
        }
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
        testCase4();
        testCase5();
    }

    public static void testCase1() {
        int[] nums = { 1, 2, 3, 3, 4, 4, 5 };

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().deleteDuplicates(link);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase2() {
        int[] nums = { 1, 1, 1, 2, 3 };

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().deleteDuplicates(link);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase3() {
        int[] nums = { 1, 1 };

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().deleteDuplicates(link);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase4() {
        int[] nums = { 1, 1, 2 };

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().deleteDuplicates(link);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase5() {
        int[] nums = { 1, 2, 2 };

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().deleteDuplicates(link);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }
}

旋转链表

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
给你一个链表的头结点 head ，旋转链表，将链表每个结点向右移动 k 个位置。

 

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,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
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        if (k <= 0) {
            return head;
        }
        
        ListNode t = null; // 保存旧链表的末尾

        int c = 0;

        ListNode p = head;
        while (p != null) {
            t = p;

            c++;
            p = p.next;
        }

        k = k % c;
        if (k <= 0) {
            return head;
        }

        int m = c - k;

        p = head;
        for (int i = 0; i < m - 1; i++) {
            p = p.next;
        }

        // 分割为两个链表
        ListNode l = p.next;
        p.next = null;

        // 合并分割后的两个链表（逆序）
        t.next = head;
        head = l;

        return head;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public static ListNode genLinkedList(int[] nums, boolean withHead, int loopPos) {
            if (nums.length == 0) {
                return null;
            }

            int val = withHead ? Integer.MIN_VALUE : nums[0];
            ListNode head = new ListNode(val);

            ListNode loop = withHead ? null : loopPos == 0 ? head : null;

            int b = withHead ? 0 : 1;
            ListNode p = head;
            for (int i = b; i < nums.length; i++) {
                p.next = new ListNode(nums[i]);
                p = p.next;

                if (loopPos == i) {
                    loop = p;
                }
            }

            if (loop != null) {
                p.next = loop;
            }

            return head;
        }

        public static ListNode genLinkedListWithHeadNode(int[] nums) {
            return genLinkedList(nums, true, -1);
        }

        public static ListNode genLinkedListWithoutHeadNode(int[] nums) {
            return genLinkedList(nums, false, -1);
        }

        public static ListNode genLoopedLinkedListWithHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, true, pos);
        }

        public static ListNode genLoopedLinkedListWithoutHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, false, pos);
        }

        public static int getCount(ListNode head, boolean withHead) {
            ListNode p = withHead ? head.next : head;

            int c = 0;
            while (p != null) {
                c++;
                p = p.next;
            }

            return c;
        }

        public static int[] toArray(ListNode head, boolean withHead) {
            int c = getCount(head, withHead);
            int[] nums = new int[c];

            ListNode p = withHead ? head.next : head;

            int k = 0;
            while (p != null) {
                nums[k] = p.val;

                k++;
                p = p.next;
            }

            return nums;
        }

        public static int[] toArrayWithHeadNode(ListNode head) {
            return toArray(head, true);
        }

        public static int[] toArrayWithoutHeadNode(ListNode head) {
            return toArray(head, false);
        }
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 1, 2, 3, 4, 5 };
        int k = 2;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().rotateRight(link, k);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase2() {
        int[] nums = { 0, 1, 2 };
        int k = 4;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().rotateRight(link, k);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }
}

分隔链表

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给你一个链表的头结点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的结点都出现在 大于或等于 x 的结点之前。

你应当 保留 两个分区中每个结点的初始相对位置。

 

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：

输入：head = [2,1], x = 2
输出：[1,2]
 

提示：

链表中结点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200

题目解答

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode l1 = new ListNode(0);
        ListNode l2 = new ListNode(0);

        ListNode t1 = l1; // 保存合并时第1个链表的末尾
        ListNode t2 = l2; // 保存合并时第2个链表的末尾

        ListNode p = head;
        while (p != null) {
            if (p.val < x) {
                t1.next = p;
                t1 = t1.next;
            } else {
                t2.next = p;
                t2 = t2.next;
            }

            p = p.next;
        }

        // 分割为两个链表
        t1.next = null;
        t2.next = null;

        // 合并分割后的两个链表
        t1.next = l2.next;
        head = l1.next;

        return head;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        public static ListNode genLinkedList(int[] nums, boolean withHead, int loopPos) {
            if (nums.length == 0) {
                return null;
            }

            int val = withHead ? Integer.MIN_VALUE : nums[0];
            ListNode head = new ListNode(val);

            ListNode loop = withHead ? null : loopPos == 0 ? head : null;

            int b = withHead ? 0 : 1;
            ListNode p = head;
            for (int i = b; i < nums.length; i++) {
                p.next = new ListNode(nums[i]);
                p = p.next;

                if (loopPos == i) {
                    loop = p;
                }
            }

            if (loop != null) {
                p.next = loop;
            }

            return head;
        }

        public static ListNode genLinkedListWithHeadNode(int[] nums) {
            return genLinkedList(nums, true, -1);
        }

        public static ListNode genLinkedListWithoutHeadNode(int[] nums) {
            return genLinkedList(nums, false, -1);
        }

        public static ListNode genLoopedLinkedListWithHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, true, pos);
        }

        public static ListNode genLoopedLinkedListWithoutHeadNode(int[] nums, int pos) {
            return genLinkedList(nums, false, pos);
        }

        public static int getCount(ListNode head, boolean withHead) {
            ListNode p = withHead ? head.next : head;

            int c = 0;
            while (p != null) {
                c++;
                p = p.next;
            }

            return c;
        }

        public static int[] toArray(ListNode head, boolean withHead) {
            int c = getCount(head, withHead);
            int[] nums = new int[c];

            ListNode p = withHead ? head.next : head;

            int k = 0;
            while (p != null) {
                nums[k] = p.val;

                k++;
                p = p.next;
            }

            return nums;
        }

        public static int[] toArrayWithHeadNode(ListNode head) {
            return toArray(head, true);
        }

        public static int[] toArrayWithoutHeadNode(ListNode head) {
            return toArray(head, false);
        }
    }

    public static class ArrayUtils {
        public static void printArray(int[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(int[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(int[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(Integer[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(Integer[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(Integer[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }

        public static void printArray(String[] array) {
            System.out.println(java.util.Arrays.toString(array));
        }

        public static void printArray(String[] array, int len) {
            System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(array, len)));
        }

        public static void printArrays(String[][] arrays) {
            System.out.println(java.util.Arrays.deepToString(arrays));
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        int[] nums = { 1, 4, 3, 2, 5, 2 };
        int x = 3;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().partition(link, x);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }

    public static void testCase2() {
        int[] nums = { 2, 1 };
        int x = 2;

        ListNode link = ListNode.genLinkedListWithoutHeadNode(nums);
        ListNode result = new Solution().partition(link, x);
        ArrayUtils.printArray(ListNode.toArrayWithoutHeadNode(result));
    }
}

LRU缓存机制

题目描述

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
请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

 

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4
 

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

题目解答

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
public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部结点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的结点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部结点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

困难

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
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

 

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

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

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
 

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

题目解答

1
//

TODO：K个一组翻转链表

只想买包辣条