#26. Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a one-sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
if (p1 == null && p2 == null) {
return null;
}
ListNode result = new ListNode(); // first node is artificial
ListNode pRes = result;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
pRes = append(pRes, p1.val);
p1 = p1.next;
} else {
pRes = append(pRes, p2.val);
p2 = p2.next;
}
}
while (p1 != null) {
pRes = append(pRes, p1.val);
p1 = p1.next;
}
while (p2 != null) {
pRes = append(pRes, p2.val);
p2 = p2.next;
}
return result.next;
}
private ListNode append(ListNode pRes, int data) {
ListNode node = new ListNode(data);
pRes.next = node;
return node;
}
}
#27. Merge k Sorted Lists
You are given an array of k linked-lists lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.
public ListNode mergeKLists_2_by_2(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
List<ListNode> partials = Arrays.asList(lists); // listele partiale, initial toate din lists
List<ListNode> res = new ArrayList<>(); // rezultatul combinarii 2 cate 2
int index = 0; // pornim cu index = 0, len-1
while (true) {
ListNode firstList = partials.get(index);
boolean hasSecondList = index + 1 < partials.size();
ListNode secondList = hasSecondList ? partials.get(index+1) : null;
res.add(mergeTwoLists(firstList, secondList));
index += hasSecondList ? 2 : 1; // incrementare index
if (index >= partials.size()) { // daca s-au procesat toate listele partiale
if (res.size() == 1) { // si avem o singura lista rezultata
return res.get(0); // s-a terminat procesarea
}
partials = res; // re-proceseaza rezultatele partiale
res = new ArrayList<>(); // reseteaza lista rezultata
index = 0; // ia-o de la capat
}
}
}
public ListNode mergeKLists_using_mergeTwoLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
ListNode result = lists[0]; // idee: adauga la prima lista a doua, a treia, etc
for (int i = 1; i < lists.length; i++) {
result = mergeTwoLists(result, lists[i]);
}
return result;
}
#28. Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if (n <= 0) {return head; // n too small}ListNode p1 = head, p2 = head;for (int i=0; i<n; i++) { // p2 will get at distance n from p1if (p2 != null) {p2 = p2.next;} else {return head; // n too large}}if (p2 == null) {// n-th node from the end is headhead = p1.next;p1.next = null;return head;}// p1 and p2 go one step at a time until p2 gets to the last positionwhile (p2 != null && p2.next != null) {p1 = p1.next;p2 = p2.next;}// remove p1.next// if p2 was null, then we would have deleted p1 (but then no access to its previous node)ListNode deleted = p1.next;p1.next = p1.next.next;deleted.next = null;return head;}}
#29. Reorder List
You are given the head of a singly linked list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
class Solution {private void swap(ListNode currentLeft, ListNode beforeCurrentRight) {ListNode next = currentLeft.next;currentLeft.next = beforeCurrentRight.next;currentLeft.next.next = next;beforeCurrentRight.next = null;}public void reorderList(ListNode head) { // no value swap; only full node swapif (head == null) {return;}ListNode p1 = head, p2 = head;Stack<ListNode> stack = new Stack<>();while (p2.next != null) {stack.push(p2);p2 = p2.next;}int halfSize = stack.size() / 2;if (stack.size() % 2 == 1) {halfSize++;}while (stack.size() > halfSize) {p2 = stack.pop();if (p1 == p2) {break;}swap(p1, p2);if (p1.next == null || p1.next.next == null) {break;}p1 = p1.next.next;}}}
