SouthLeetCode-打卡24年02月第1周
// Date : 2024/02/01 ~ 2024/02/04
034.合并两个有序链表
(1) 题目描述
| 034 | #LeetCode.21. | #北岸计划 | 2024/02/01 |
|---|
将两个升序链表合并为一个新的 升序 链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
(2) 题解代码
class Solution {
private ListNode mergeLists(ListNode curr, ListNode list) {
while (list != null) {
int curVal = list.val;
curr.next = new ListNode(curVal);
curr = curr.next;
list = list.next;
}
return curr;
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode curr = dummy;
while (list1 != null && list2 != null) {
boolean condition = list1.val < list2.val;
int curVal = condition ? list1.val : list2.val;
curr.next = new ListNode(curVal);
curr = curr.next;
if (condition) {
list1 = list1.next;
} else {
list2 = list2.next;
}
}
curr = mergeLists(curr, list1);
curr = mergeLists(curr, list2);
return dummy.next;
}
}
035.合并K个升序链表
(1) 题目描述
| 035 | #LeetCode.23. | #北岸计划 | 2024/02/01 |
|---|
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
(2) 题解代码
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int size = lists.length;
ListNode curr;
int curVal;
ListNode dummy = new ListNode();
List<Integer> result = new ArrayList<>();
for(int i=0 ; i<size ; i++){
curr = lists[i];
while(curr != null){
curVal = curr.val;
result.add(curVal);
curr = curr.next;
}
}
Collections.sort(result);
int length = result.size();
ListNode resDummy = new ListNode();
curr = resDummy;
for(int k=0 ; k<length ; k++){
curr.next = new ListNode(result.get(k));
curr = curr.next;
}
return resDummy.next;
}
}
036.链表的中间结点Ⅰ
(1) 题目描述
| 036 | #LeetCode.NULL. | #北岸计划 | 2024/02/03 |
|---|
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第一个中间结点。
(2) 题解代码
public class MiddleNodeFor1 implements MiddleNode {
@Override
public ListNode middleNode(ListNode head){
ListNode dummy = new ListNode();
dummy.next = head;
ListNode slow = dummy;
ListNode fast = head;
while(fast != null){
slow = slow.next;
fast = fast.next;
fast = fast != null ? fast.next : fast;
}
return slow;
}
}
037.链表的中间结点Ⅱ
(1) 题目描述
| 037 | #LeetCode.876. | #北岸计划 | 2024/02/03 |
|---|
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
(2) 题解代码
class Solution {
public ListNode middleNode(ListNode head) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
while(fast != null){
slow = slow.next;
fast = fast.next;
fast = fast != null ? fast.next : fast;
}
return slow;
}
}
038.分隔链表
(1) 题目描述
| 038 | #LeetCode.86. | #北岸计划 | 2024/02/04 |
|---|
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
(2) 题解代码
class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null) return null;
ListNode curr = head;
List<Integer> list = new ArrayList();
int curVal;
while(curr != null){
list.add(curr.val);
curr = curr.next;
}
List<Integer> sList = new ArrayList();
for(int i=0 ; i<list.size() ; i++){
curVal = list.get(i);
if(curVal < x){
sList.add(curVal);
list.remove(i);
i--;
}
}
for(int j=0 ; j<list.size() ; j++){
curVal = list.get(j);
sList.add(curVal);
}
ListNode newHead = new ListNode(sList.get(0));
curr = newHead;
for(int k=1 ; k<sList.size() ; k++){
curVal = sList.get(k);
curr.next = new ListNode(curVal);
curr = curr.next;
}
return newHead;
}
}
