50 DSA-Questions: Lists #26, #27, #28, #29

#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 p1
            if (p2 != null) {
                p2 = p2.next;
            } else {
                return head; // n too large
            }
        }
        if (p2 == null) { 
            // n-th node from the end is head
            head = p1.next;
            p1.next = null;
            return head;
        }
        // p1 and p2 go one step at a time until p2 gets to the last position
        while (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 swap
        if (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;
        }
    }
}