假如p, q在root同一侧，则继续递归这一侧，否则返回当前节点（可能当前节点为p,q之一，也可能在不同侧） 如果是BST,可以保存到p, q的路径，然后找到链表最后一个公共节点即可235. Lowest Common Ancestor of a Binary Search Tree
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q); if(p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q); return root; } };换着遍历，当遍历到长度为da（a独有） + db（b独有） + ab（ab公共部分）时，两指针会合，
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { auto p = headA; auto q = headB; while(p != q){ p = p ? p->next : headB; q = q ? q->next : headA; } return p; } };还有一种方法是计算链表长度的不谈了，我当时的做法时用异或+反转链表, 异或的结果就是第一个交点
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverse(ListNode* h, intptr_t & pivot){ auto cur = h; ListNode* prev = NULL; while(cur != NULL){ pivot = pivot ^ (intptr_t)(cur); auto t = cur->next; cur->next = prev; prev = cur; cur = t; } return prev; } ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { intptr_t pivot = 0; auto end = reverse(headA, pivot); auto b = reverse(headB, pivot); auto a = reverse(end, pivot); if(b == headA){ return (ListNode*)pivot; } else { reverse(b, pivot); return NULL; } } };转载于:https://www.cnblogs.com/qbits/p/11165298.html
