public class Node {
private Integer data;
private Node next;
public Node() {
// empty
}
public Node(Integer data) {
this.data = data;
this.next = null;
}
public Node(Integer data, Node next) {
this.data = data;
this.next = next;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public static void printList(Node head) {
Node node = head;
while (node != null) {
System.out.print(node.getData() + " ");
node = node.getNext();
}
System.out.println();
}
public static Node buildFrom(int[] elements) {
if (elements.length == 0) {
return null;
}
Node head = new Node(elements[0]);
Node node = head;
for (int i=1; i<elements.length; i++) {
Node newNode = new Node(elements[i]);
node.setNext(newNode);
node = newNode;
}
return head;
}
}
#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.
#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 class Exercise26 {
private static final int[] FIRST_LIST = {0,1,2,5,8};
private static final int[] SECOND_LIST = {1,3,7,8};
private Node mergeTwo(Node p1, Node p2) {
Node result = new Node();
Node pRes = result;
while (p1 != null && p2 != null) {
if (p1.getData() < p2.getData()) {
pRes = addToResult(pRes, p1.getData());
p1 = p1.getNext();
} else {
pRes = addToResult(pRes, p2.getData());
p2 = p2.getNext();
}
}
while (p1 != null) {
pRes = addToResult(pRes, p1.getData());
p1 = p1.getNext();
}
while (p2 != null) {
pRes = addToResult(pRes, p2.getData());
p2 = p2.getNext();
}
return result;
}
private static final int[][] LIST_OF_LISTS = {{1,4,7}, {2,5,8}, {0, 5, 6}};
private Node mergeK() {
Node p1 = Node.buildFrom(LIST_OF_LISTS[0]);
Node p2;
for (int i = 0; i < LIST_OF_LISTS.length - 1; i++) {
p2 = Node.buildFrom(LIST_OF_LISTS[i+1]);
p1 = mergeTwo(p1, p2);
}
return p1;
}
private Node addToResult(Node pRes, int data) {
if (pRes.getData() == null) {
pRes.setData(data);
return pRes;
}
Node node = new Node(data);
pRes.setNext(node);
return node;
}
public static void main(String args[]) {
Node p1 = Node.buildFrom(FIRST_LIST);
Node p2 = Node.buildFrom(SECOND_LIST);
Node result = new Exercise26().mergeTwo(p1, p2);
System.out.println("Merged 2 lists:");
Node.printList(result);
System.out.println();
result = new Exercise26().mergeK();
System.out.printf("Merged k=%d lists:%n", LIST_OF_LISTS[0].length);
Node.printList(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.
public class Exercise28 {
private static final int[] elements = {1, 2, 3, 4, 5};
private static final int N = 1;
private Node removeNthNodeFromTheEnd(Node head, int n) {
if (n <= 0) {
System.out.println("N is too small!");
return head;
}
Node p1 = head, p2 = head;
for (int i=0; i<n; i++) {
if (p2 != null) {
p2 = p2.getNext();
} else {
System.out.println("N is too large!");
return head;
}
}
if (p2 == null) {
head = p1.getNext();
p1.setNext(null);
return head;
}
while (p2 != null && p2.getNext() != null) {
p1 = p1.getNext();
p2 = p2.getNext();
}
Node deleted = p1.getNext();
p1.setNext(p1.getNext().getNext());
deleted.setNext(null);
return head;
}
public static void main(String args[]) {
Node head = Node.buildFrom(elements);
Node result = new Exercise28().removeNthNodeFromTheEnd(head, N);
Node.printList(result);
}
}
#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.
public class Exercise29 {
private static final int[] LIST = {1,2,3,4,5}; // -> reordered {1,5,2,4,3}
// private static final int[] LIST = {1,2,3,4,5,6}; // -> reordered {1,6,2,5,3,4}
// private static final int[] LIST = {1,2,3}; // -> reordered {1,3,2}
// private static final int[] LIST = {1,2}; // -> reordered {1,2}
// private static final int[] LIST = {1}; // -> reordered {1}
// private static final int[] LIST = {}; // -> reordered {}
private void swap(Node currentLeft, Node beforeCurrentRight) {
Node next = currentLeft.getNext();
currentLeft.setNext(beforeCurrentRight.getNext());
currentLeft.getNext().setNext(next);
beforeCurrentRight.setNext(null);
}
private void reorderList(Node head) { // no value swap; only full node swap
if (head == null) {
return;
}
Node p1 = head, p2 = head;
Stack<Node> stack = new Stack<>();
while (p2.getNext() != null) {
stack.push(p2);
p2 = p2.getNext();
}
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.getNext() == null || p1.getNext().getNext() == null) {
break;
}
p1 = p1.getNext().getNext();
}
}
public static void main(String args[]) {
Node head = Node.buildFrom(LIST);
new Exercise29().reorderList(head);
Node.printList(head);
}
}
