Reverse a single linked list using single pointer iteratively and recursively

(Recursive)
struct list * reverse_ll( struct list * head)
{
struct list * temp = NULL;

if ( head == NULL)
return NULL;
if ( head->next == NULL )
return head;

temp = reverse_ll ( head->next );
head->next -> next = head;
head->next = NULL;
return temp;
}

int main()
{
...
head = reverse_ll(head);
...
}
____________________________________________________________________
(Iterative)

#define pointer_swap( a, b) ((int)(a))^=((int)(b))^=((int)(a))^=((int)(b))

struct list * reverse_ll( struct list * head)
{
struct list * temp = NULL;
if (head && head->next) {
temp = head->next;
head->next = NULL;
} else {
return head;
}
while (temp->next) {
pointer_swap(head, temp->next);
pointer_swap(head,temp);
}
temp->next = head;
//head = temp;
return temp;
}
____________________________________________________________________



. Minimized version of my code.
#define pointer_swap(a,b) ((int)(a)) ^= ((int)(b)) ^= ((int)(a)) ^= ((int)(b))

struct list * reverse_ll(struct list * head)
{
struct list * temp = NULL;

while(head) {
pointer_swap(temp,head->next);
pointer_swap(temp,head);
}
return temp;
}

Find the two repeating elements in a given array

Find the two repeating elements in a given array June 9, 2010 You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers. For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5 The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2. Method 1 (Basic) Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop. This method doesn’t use the other useful data provided in questions like range of numbers is between 1 to n and there are only two repeating elements. view source print? #include #include void printRepeating(int arr[], int size) { int i, j; printf(" Repeating elements are "); for(i = 0; i <> for(j = i+1; j <> if(arr[i] == arr[j]) printf(" %d ", arr[i]); } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printRepeating(arr, arr_size); getchar(); return 0; } Time Complexity: O(n*n) Auxiliary Space: O(1) Method 2 (Use Count array) Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate. This method uses the range given in the question to restrict the size of count[], but doesn’t use the data that there are only two repeating elements. view source print? #include #include void printRepeating(int arr[], int size) { int *count = (int *)calloc(sizeof(int), (size - 2)); int i; printf(" Repeating elements are "); for(i = 0; i <> { if(count[arr[i]] == 1) printf(" %d ", arr[i]); else count[arr[i]]++; } } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printRepeating(arr, arr_size); getchar(); return 0; } Time Complexity: O(n) Auxiliary Space: O(n) Method 3 (Make two equations) We have to find two numbers, so to unknowns. We know the sum of n numbers is n(n+1)/2 and product is n!. Make two equations using these sum and product formulas, and get values of two unknowns using the two equations. Let summation of all numbers in array be S and product be P Let the numbers which are being repeated are X and Y. X + Y = S – n(n+1)/2 XY = P/n! Using above two equations, we can find out X and Y. For array = 4 2 4 5 2 3 1, we get S = 21 and P as 960. X + Y = 21 – 15 = 6 XY = 960/5! = 8 X – Y = sqrt((X+Y)^2 – 4*XY) = sqrt(4) = 2 Using below two equations, we easily get X = (6 + 2)/2 and Y = (6-2)/2 X + Y = 6 X – Y = 2 Thanks to geek4u for suggesting this method. As pointed by Beginer , there can be addition and multiplication overflow problem with this approach. The methods 3 and 4 use all useful information given in the question view source print? #include #include #include /* function to get factorial of n */ int fact(int n); void printRepeating(int arr[], int size) { int S = 0; /* S is for sum of elements in arr[] */ int P = 1; /* P is for product of elements in arr[] */ int x, y; /* x and y are two repeating elements */ int D; /* D is for difference of x and y, i.e., x-y*/ int n = size - 2, i; /* Calculate Sum and Product of all elements in arr[] */ for(i = 0; i <> { S = S + arr[i]; P = P*arr[i]; } S = S - n*(n+1)/2; /* S is x + y now */ P = P/fact(n); /* P is x*y now */ D = sqrt(S*S - 4*P); /* D is x - y now */ x = (D + S)/2; y = (S - D)/2; printf("The two Repeating elements are %d & %d", x, y); } int fact(int n) { return (n == 0)? 1 : n*fact(n-1); } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printRepeating(arr, arr_size); getchar(); return 0; } Time Complexity: O(n) Auxiliary Space: O(1) Method 4 (Use XOR) Thanks to neophyte for suggesting this method. The approach used here is similar to method 2 of this post. Let the repeating numbers be X and Y, if we xor all the elements in the array and all integers from 1 to n, then the result is X xor Y. The 1’s in binary representation of X xor Y is corresponding to the different bits between X and Y. Suppose that the kth bit of X xor Y is 1, we can xor all the elements in the array and all integers from 1 to n, whose kth bits are 1. The result will be one of X and Y. view source print? void printRepeating(int arr[], int size) { int xor = arr[0]; /* Will hold xor of all elements */ int set_bit_no; /* Will have only single set bit of xor */ int i; int n = size - 2; int x = 0, y = 0; /* Get the xor of all elements in arr[] and {1, 2 .. n} */ for(i = 0; i <> xor ^= arr[i]; for(i = 1; i <= n; i++) xor ^= i; /* Get the rightmost set bit in set_bit_no */ set_bit_no = xor & ~(xor-1); /* Now divide elements in two sets by comparing rightmost set bit of xor with bit at same position in each element. */ for(i = 0; i <> { if(arr[i] & set_bit_no) x = x ^ arr[i]; /*XOR of first set in arr[] */ else y = y ^ arr[i]; /*XOR of second set in arr[] */ } for(i = 1; i <= n; i++) { if(i & set_bit_no) x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/ else y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */ } printf("\n The two repeating elements are %d & %d ", x, y); } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printRepeating(arr, arr_size); getchar(); return 0; } Method 5 (Use array elements as index) Thanks to Manish K. Aasawat for suggesting this method. traverse the list for i= 1st to n+2 elements { check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // i.e., A[abs(A[i])] is negative this element (ith element of list) is a repetition } Example: A[] = {1,1,2,3,2} i=1 ; A[abs(A[1])] i.e,A[1] is positive ; so make it negative ; so list now is {-1,1,2,3,2} i=2 ; A[abs(A[2])] i.e., A[1] is negative ; so A[i] i.e., A[2] is repetition, now list is {-1,1,2,3,2} i=3 ; list now becomes {-1,-1,2,3,2} and A[3] is not repeated now list becomes {-1,-1,-2,3,2} i=4 ; and A[4]=3 is not repeated i=5 ; we find A[abs(A[i])] = A[2] is negative so A[i]= 2 is a repetition, This method modifies the original array. view source print? #include #include void printRepeating(int arr[], int size) { int i; printf("\n The repeating elements are"); for(i = 0; i <> { if(arr[abs(arr[i])] > 0) arr[abs(arr[i])] = -arr[abs(arr[i])]; else printf(" %d ", abs(arr[i])); } } int main() { int arr[] = {1, 3, 2, 2, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printRepeating(arr, arr_size); getchar(); return 0; } The problem can be solved in linear time using other method also

Reverse a Linked List in groups of given size

Reverse a Linked List in groups of given size June 14, 2010 Given a linked list, write a function to reverse every k nodes (where k is an input to the function). Example: Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3 Output: 3->2->1->6->5->4->8->7->NULL. Inputs: 1->2->3->4->5->6->7->80->NULL and k = 5 Output: 5->4->3->2->1->8->7->6->NULL. Algorithm: reverse(head, k) 1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev. See this post for reversing a linked list. 2) head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */ 3) return prev /* prev becomes the new head of the list (see the diagrams of iterative method of this post) */ view source print? #include #include /* Link list node */ struct node { int data; struct node* next; }; /* Reverses the linked list in groups of size k and returns the pointer to the new head node */ struct node *reverse (struct node *head, int k) { struct node* current = head; struct node* next; struct node* prev = NULL; int count = 0; /*reverse first k nodes of the linked list */ while (current != NULL && count <> { next = current->next; current->next = prev; prev = current; current = next; count++; } /* next is now a pointer to (k+1)th node Recursively call for the list starting from current. And make rest of the list as next of first node */ if(next != NULL) { head->next = reverse(next, k); } /* prev is new head of the input list */ return prev; } /* UTILITY FUNCTIONS */ /* Function to push a node */ void push(struct node** head_ref, int new_data) { /* allocate node */ struct node* new_node = (struct node*) malloc(sizeof(struct node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print linked list */ void printList(struct node *node) { while(node != NULL) { printf("%d ", node->data); node = node->next; } } /* Drier program to test above function*/ int main(void) { /* Start with the empty list */ struct node* head = NULL; /* Created Linked list is 1->2->3->4->5->6->7->8 */ push(&head, 8); push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); printf("\n Given linked list \n"); printList(head); head = reverse(head, 3); printf("\n Reversed Linked list \n"); printList(head); getchar(); } return(0); Time Complexity: O(n) where n is the number of nodes in the given list.