mshah2
BAN USERstatic void Reverse(struct node** headRef) {
struct node* result = NULL;
struct node* current = *headRef;
struct node* next;
while (current != NULL) {
next = current->next; // tricky: note the next node
current->next = result; // move the node onto the result
result = current;
current = next;
}
*headRef = result;
}
void RecursiveReverse(struct node** headRef) {
struct node* first;
struct node* rest;
if (*headRef == NULL) return; // empty list base case
first = *headRef; // suppose first = {1, 2, 3}
rest = first->next; // rest = {2, 3}
if (rest == NULL) return; // empty rest base case
RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3}
// after: rest = {3, 2}
// put the first elem on the end of the list
first->next->next = first;
first->next = NULL; // (tricky step -- make a drawing)
*headRef = rest; // fix the head pointer
}
All we need to do is to first calculate len=len1-len2 (len1>len2, as discussed above). Point p1 and p2 to list1 (the longer one) and list2 respectively. Then step only p1 for "len" no. of nodes. After this we are guaranteed that p1 and p2 are equidistant from the common node. So now start stepping p1 and p2 simultaneously until p1==p2. This will the common node. This is a simple O(n) solution.
- mshah2 September 07, 2008