排序链表 重排链表 最接近目标价格的甜点成本 环形链表

148. 排序链表

弄到数组里，数组排序，再弄个新链表
List list = new ArrayList<>();
ListNode pre = head;
while(pre != null) {
list.add(pre.val);
pre = pre.next;
}
int[] ans = new int[list.size()];
for(int i = 0; i < list.size(); i++) {
ans[i] = list.get(i);
}
Arrays.sort(ans);
ListNode root = new ListNode(0);
head = root;
for(int i : ans) {
ListNode cur = new ListNode(i);
root.next = cur;
root = root.next;
}
return head.next;

143. 重排链表

List list = new ArrayList<>();直接将节点存储在list中
ListNode root = head;
while(root != null) {
list.add(root);
root = root.next;
}
int left = 0;
int right = list.size() - 1;
while(left < right) {
list.get(left).next = list.get(right);交替
left++;
if(left == right) break;注意细节
list.get(right).next = list.get(left);
right--;
}
list.get(left).next = null;

1774. 最接近目标价格的甜点成本

int ans = Integer.MAX_VALUE;
public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
for(int i : baseCosts) {
ans = Math.min(ans, i);
}
/ans = Arrays.stream(baseCosts).min().getAsInt();/
for(int i : baseCosts) {
dfs(toppingCosts, 0, i, target);记录不同起始值，更新到的答案
}
return ans;
}
public void dfs(int[] toppingCosts, int len, int cur, int target) {
if(Math.abs(ans - target) < cur - target) return ;细节：若是已经超过了target且差值还大于ans的可以直接剪去。因为后面的添加只会让差值越来越大
else if(Math.abs(ans - target) >= Math.abs(cur - target)) {
if(Math.abs(ans - target) > Math.abs(cur - target)) {
ans = cur;
}else {误差一样，选择成本少的
ans = Math.min(ans, cur);
}
}
if(len == toppingCosts.length) {
return ;
}
dfs(toppingCosts, len + 1, cur + toppingCosts[len] * 2, target);
dfs(toppingCosts, len + 1, cur + toppingCosts[len], target);
dfs(toppingCosts, len + 1, cur, target);
}

141. 环形链表

Set set = new HashSet<>();
if(head == null) return false;
while(head.next != null) {
if(!set.add(head)) {细节：set中如果添加已添加的元素，会返回false
return true;
}
head = head.next;
}
return false;