elus
BAN USERhttp://www.teamten.com/lawrence/writings/reverse_a_linked_list.html
C:
void reverse(node **head)
{
node *prev = NULL;
while (NULL != *head) {
node *next = (*head)->next;
(*head)->next = prev;
prev = *head;
*head = next;
}
*head = prev;
}
or:
void reverse(node **head)
{
node *new_head = NULL;
while (NULL != *head) {
node *elem = *head;
*head = (*head)->next;
elem->next = new_head;
new_head = elem;
}
*head = new_head;
}
Java:
public static Node reverse(Node head) {
Node prev = null;
while (head != null) {
Node next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
or:
public static Node reverse(Node head) {
Node newHead = null;
while (head != null) {
Node elem = head;
head = head.next;
elem.next = newHead;
newHead = elem;
}
return newHead;
}
Note that above solutions can be easily transformed into recursive ones.
- elus August 10, 2013This code work only for n.length <= 31, there's also no handling of sum integer overflow and it prints the same subset multiple times if there are duplicates in n array. Slightly improved (but probably slightly slower too) version:
public static void printSubSets(int nums[], int k){
Set<Integer> set = new HashSet<Integer>();
for (int num : nums) {
set.add(num);
}
for (BigInteger bi = BigInteger.ONE;
bi.bitLength() <= set.size();
bi = bi.add(BigInteger.ONE)) {
int sum = 0;
int i = 0;
Set<Integer> subset = new HashSet<Integer>();
for (int num : set) {
if (bi.testBit(i++)) {
subset.add(num);
if (sum < k) {
sum += num;
}
}
}
if (sum >= k) {
System.out.println(subset);
}
}
}
This can be improved by using Gray code for subsets generation - since two successive values in Gray code differ in only one bit we can easily reuse subset from previous iteration step (and simply add or remove one number in it). Still - printing generated subset is O(m) (where m in a length of generated subset, which is ~0.5n in average), so the overall algorithm worst case time complexity stays at O(n * n^2).
- elus August 12, 2013Generation of sets in descending sum order would improve best case performance, but wouldn't change the worst case performance.