算法双指针
hiriki206.反转链表
leetcode题目链接
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->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
|
class Solution {
public ListNode reverseList(ListNode head) {
ListNode current = head;
ListNode pre = null;
while(current!=null){
ListNode temp = current.next;
current.next = pre;
pre = current;
current = temp;
}
return pre;
}
}
|
19.删除链表的倒数第N个节点
leetcode题目链接
题意：给你一个链表，删除链表的倒数第 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]
思路草稿
题解
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
|
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode visual = new ListNode();
visual.next = head;
ListNode slow = visual, fast = visual;
for(int i = 0;i < n;i++){
fast = fast.next;
}
while(fast.next!=null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return visual.next;
}
}
|
142.环形链表II
leetcode题目链接
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 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
|
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
ListNode index1 = head;
ListNode index2 = slow;
while(index1!=index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
|
15.三数之和
leetcode题目链接
题意：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 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
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
if(nums[0] > 0){
return result;
}
for(int i = 0;i<nums.length;i++){
if(i>0 && nums[i]==nums[i-1]){
continue;
}
int left = i+1;
int right = nums.length-1;
while(left<right){
int sum = nums[i] + nums[left] + nums[right];
if(sum>0){
right--;
} else if(sum<0){
left++;
} else {
result.add(Arrays.asList(nums[i],nums[left],nums[right]));
while(left<right&&nums[right]==nums[right-1]){
right--;
}
while(left<right&&nums[left]==nums[left+1]){
left++;
}
left++;
right--;
}
}
}
return result;
}
}
|
18.四数之和
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 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
| class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
if(nums[0]>0&&nums[0]>target){
return result;
}
for(int i = 0 ;i<nums.length;i++){
if(i>0&&nums[i]==nums[i-1]){
continue;
}
for(int j = i+1;j<nums.length;j++){
if(j>i+1 && nums[j]==nums[j-1]){
continue;
}
int left = j+1;
int right = nums.length-1;
while(left<right){
int sum = nums[i]+nums[j]+nums[left]+nums[right];
if(sum>target){
right--;
} else if(sum<target){
left++;
} else{
result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
while(left<right&&nums[right]==nums[right-1]){
right--;
}
while(left<right&&nums[left]==nums[left+1]){
left++;
}
left++;
right--;
}
}
}
}
return result;
}
}
|
