Solutions to sample midterm

12)
class Node
{
int val;
Node next;
}

13)
a) class SLL
{
Node head, tail;
int size;
// constructor present but not given here
// choose not to make header or trailer
}

b) void insertBefore(Node n, int x)
{
Node m = new Node(x);

if (n==head)
{
m.next = n;
head = m;
}
else
{
// traverse from head
for (Node cur = head; cur.next!=n; cur=cur.next)
; // do nothing
cur.next=m;
m.next=n;

}
size++;
}

c) void insertAfter(Node n, int x)
{
Node m=new Node(x);
m.next = n.next;
n.next = m;

if (n==tail)
m = tail;
size++;
}

d) void remove(int value)
{
if (size==0)
return;
Node prev = null;
for(Node cur = head; cur != null && cur.val != value; prev=cur, cur=cur.next)
; // do nothing
if (prev==null) // found item at head
{
head=head.next;
size--;
}
else if (cur != null && cur.val == value) // item found
{
prev.next = cur.next; // leapfrog
}
if (prev.next==null)
tail=prev;
}
d) void removeSpan(Node start, Node finish)
{
start.next = finish;
}

e) void swap(Node n, Node m)
{
int temp = n.val;
n.val = m.val;
m.val = temp;
}