-
Notifications
You must be signed in to change notification settings - Fork 4
/
LinkedListUtil.java
65 lines (56 loc) · 1.92 KB
/
LinkedListUtil.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package custom.linked.list;
import custom.linked.list.SinglyLinkedList;
import custom.linked.list.SinglyLinkedList.Node;
public class LinkedListUtil {
/**
* @param sll1 First linked list. @see {@link SinglyLinkedList}
* @param sll2 Second linked list. @see {@link SinglyLinkedList}
* @return String representation of merged linked list.
*/
public static String mergeSortedLinkedLists(SinglyLinkedList<Integer> sll1, SinglyLinkedList<Integer> sll2) {
Node<Integer> dummyNode = new Node<>();
Node<Integer> dummyNodeLast = dummyNode;
Node<Integer> start1 = sll1.getStart();
Node<Integer> start2 = sll2.getStart();
Node<Integer> i1 = start1, i2 = start2;
while(true) {
Integer smallerVal = null;
if(i1!=null && i2!=null) {
if(i1.getValue()<i2.getValue()) {
smallerVal = i1.getValue();
i1 = i1.getNext();
} else {
smallerVal = i2.getValue();
i2 = i2.getNext();
}
} else if(i1!=null) {
smallerVal = i1.getValue();
i1 = i1.getNext();
} else if(i2!=null) {
smallerVal = i2.getValue();
i2 = i2.getNext();
} else {
break;
}
Node<Integer> newNode = new Node<>(smallerVal, null);
dummyNodeLast.setNext(newNode);
dummyNodeLast = newNode;
}
String allElts="start";
Node<Integer> i;
for(i = dummyNode.getNext(); i!=null; i=i.getNext()){
allElts = allElts + "->"+i.getValue();
}
return allElts;
}
/**
* Delete a node from a singly linked list, Given only a pointer/reference to a node to be deleted.
* @param nodeToBeDeleted Pointer/reference to a node to be deleted.
*/
public static void deleteNode(Node<Integer> nodeToBeDeleted) {
Node<Integer> nextNode = nodeToBeDeleted.getNext();
nodeToBeDeleted.setValue(nextNode.getValue());
nodeToBeDeleted.setNext(nextNode.getNext());
nextNode = null;
}
}