SouthLeetCode-打卡24年02月第1周

// Date : 2024/02/01 ~ 2024/02/04

034.合并兩個有序鏈表

(1) 題目描述

034	#LeetCode.21.	#北岸計劃	2024/02/01

將兩個升序鏈表合并為一個新的 升序 鏈表并返回。

新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。

(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

給你一個鏈表數(shù)組，每個鏈表都已經(jīng)按升序排列。

請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

(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.鏈表的中間結(jié)點Ⅰ

(1) 題目描述

036	#LeetCode.NULL.	#北岸計劃	2024/02/03

給你單鏈表的頭結(jié)點 head ，請你找出并返回鏈表的中間結(jié)點。

如果有兩個中間結(jié)點，則返回第一個中間結(jié)點。

(2) 題解代碼

public class MiddleNodeFor1 implements MiddleNode {@Overridepublic 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.鏈表的中間結(jié)點Ⅱ

(1) 題目描述

037	#LeetCode.876.	#北岸計劃	2024/02/03

給你單鏈表的頭結(jié)點 head ，請你找出并返回鏈表的中間結(jié)點。

如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。

(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

給你一個鏈表的頭節(jié)點 head 和一個特定值 x ，請你對鏈表進行分隔，

使得所有 小于 x 的節(jié)點都出現(xiàn)在 大于或等于 x 的節(jié)點之前。

你應(yīng)當 保留 兩個分區(qū)中每個節(jié)點的初始相對位置。

(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;}
}